[알고리즘 문제] 백준1911 - 흙길 보수하기

문제 자체는 이해하기 어렵지 않다. N개의 물 웅덩이와 길이가L인 널빤지가 있을 때, N개의 물 웅덩이를 덮을 수 있는 널빤지의 최소 개수를 구하는 문제이다. 한마디로 모든 물웅덩이를 덮는데 필요한 최소 널빤지 개수를 구하는 문제이다.

 

그리디 알고리즘으로 분류되어 있었기 때문에, 뭔가 아주 간단한 규칙이 있을 거라 생각했다. 처음에는 그 규칙을 찾으려고 했었는데, 생각해보니 그냥 처음부터 덮는 방법으로 하면 되는 문제였다.

 

문제 해결 방법은,

1. 웅덩이들을 시작점을 기준으로 정렬한다.

2. 현재 구간(웅덩이 시작-끝)동안 필요한 널빤지 개수를 구한다.

3. 시작점+널빤지의 길이가 만약 다음 웅덩이의 시작점보다 작으면 1의 과정을 반복하지만, 크거나 같다면 현재 시작점+널빤지의 길이를 시작점으로 다시 1의 과정을 시작한다.

 

부연 설명을 하자면, 널빤지의 길이가 4이고, 웅덩이의 위치가 각각 1~5, 6~8이라면 처음 널빤지를 하나 놓으면 1~5 , 6~10구간을 덮기 때문에 웅덩이를 모두 덮을 수 있다.

 

반면에 만약 널빤지의 길이가 7이라면 1~8의 구간을 덮는다. 이렇게 되면 첫번째 웅덩이를 모두 덮이게 되고, 널빤지는 1~8구간을 덮기 때문에 두번째 웅덩이의 6~8구간을 덮게 된다. 하지만 문제 될 것이없다. 두번쨰 웅덩이를 덮을 때는 시작점이 6이 아니라, 8부터 시작하면 되기 때문이다.

 

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 물 웅덩이 개수
        int L = sc.nextInt(); // 널빤지 길이

        Hole[] holes = new Hole[N];

        for (int i = 0; i < N; i++) {
            holes[i] = new Hole(sc.nextInt(), sc.nextInt());
        }

        Arrays.sort(holes, new Comparator<Hole>() { // start를 기준으로 정렬
            @Override
            public int compare(Hole h1, Hole h2) {
                if (h1.start > h2.start) {
                    return 1;
                } else {
                    return -1;
                }
            }
        });

        int boardCount = 0;
        int start = 0;

        for (int i = 0; i < N; i++) {

            start = Math.max(start, holes[i].start); // 널빤지가 다음 웅덩이의 시작점을 넘었는지 넘지 않았는지 확인
            int t = 0; // i번째 구덩이를 덮기 위해서 필요한 널빤지의 길이
            while (t < holes[i].end - start) {
                t += L;
            }
            boardCount = boardCount + t / L; // t/L을 하면 필요한 널빤지의 길이가 나옴
            start += t; // start에서 널빤지의 길이만큼 +
        }
        System.out.println(boardCount);
    }
}

class Hole {
    int start;
    int end;

    Hole(int start, int end) {
        this.start = start;
        this.end = end;
    }

    public void setStart(int start) {
        this.start = start;
    }
}

ㅇㅁㄴㅇㅁㄴㅇ

먼저 처음에 입력받은 물 웅덩이를 시작위치를 기준으로 정렬해준다. 

 

그리고 for문을 반복하는데, 먼저 start와 hole.[i].start두 값 중 최대값을 다시 start에 넣는다. 이렇게 하는 이유는, start는 현재 위치에서 널빤지를 추가했을 때의 위치이기 때문에(웅덩이가 1~4이고 널빤지의 길이가 7이라면 start는 1+7=8이 된다), 만약 start가 다음 웅덩이의 위치를 침범하는 경우 start를 사용하고 그렇지 않으면 기존의 웅덩이 위치를 사용하게 된다.

 

그리고 while문을 돌면서 현재 웅덩이의 구간(end-start)을 널빤지로 덮어준다. 이때 t는 필요한 널빤지의 길이가 된다.

이후 t값을 사용하여 사용된 널빤지의 개수를 구하고, start에 t 값을 더해준다. 이렇게 해야만 현재 널빤지가 다음 웅덩이 시작점의 침범여부를 결정할 수 있기 때문이다.