[JAVA][BOJ 1911] 흙길 보수하기 - 그리디 pq

[Gold V] 흙길 보수하기 - 1911

문제 링크

성능 요약 메모리: 39344 KB, 시간: 448 ms

분류 그리디 알고리즘, 정렬, 스위핑

문제 설명

어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000,000)인 널빤지들을 충분히 가지고 있어서, 이들로 다리를 만들어 물웅덩이들을 모두 덮으려고 한다. 물웅덩이들의 위치와 크기에 대한 정보가 주어질 때, 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 구하여라.

입력

첫째 줄에 두 정수 N과 L이 들어온다.

둘째 줄부터 N+1번째 줄까지 총 N개의 줄에 각각의 웅덩이들의 정보가 주어진다. 웅덩이의 정보는 웅덩이의 시작 위치와 끝 위치로 이루어진다. 각 위치는 0 이상 1,000,000,000 이하의 정수이다. 입력으로 주어지는 웅덩이는 겹치지 않는다.

출력

첫째 줄에 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 출력한다.

---

import java.util.*;

public class Main {
    public static class Pair {
        int start, end;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int l = sc.nextInt();

        Pair[] puddle = new Pair[n+1];

        for (int i = 0; i < n; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();
            puddle[i] = new Pair(start, end);
        }

        // 입력 순서 정렬
        Arrays.sort(puddle, 0, n, Comparator.comparingInt(p-> p.start));

        int result = 0;

        for (int i = 0; i < n; i++) {
            int length = puddle[i].end - puddle[i].start;

            // 웅덩이를 널빤지 최대 길이로 덮을 수 있는 만큼 덮기
            result += (int) (length / l);

            // 마지막 웅덩이는 남은 길이가 있으면 널빤지 추가
            if (i == n-1){
                if (length % l != 0) {
                    result++;
                }
                System.out.println(result);
                return;
            }

            // 남은 거리부터 두 번째 웅덩이까지의 거리가 널빤지보다 작으면 널빤지 놓기
            if (length % l != 0) {
                puddle[i].end = puddle[i].end - length % l;

                if (puddle[i + 1].start - puddle[i].end <= l) {
                    result++;
                    puddle[i + 1].start = puddle[i].end + l;
                } else {
                    // 웅덩이까지 거리보다 널빤지가 짧으면 그냥 크기에 맞게 놓고 넘어가기
                    result++;
                }
            }
        }
    }
}

웅덩이 길이를 구해서 널빤지 최대 길이로 모두 덮을 수 있으면 덮고

아니면 남은 거리부터 두번째 웅덩이 시작점이 널빤지 최대 길이보다 직은 경우, 큰 경우 나눠서 작다면 널빤지 최대 길이로 덮고, 크면 웅덩이 길이에 맞게 덮어줬다.

널빤지 최대 길이로 덮은 경우에는 다음 웅덩이의 시작점을 갱신해주었다.

결과는 틀렸습니다.. 나는 케이스보고 답이 맞게끔 수정하면서 풀어가지구 케이스 적을 때 예외 케이스 만들어서 푸는 게 너무 어려운 것 같다 ㅠㅠ

 

그나마 비슷한 흐름의 코드를 참조해서 수정했다.

[백준 - 1911][GOLD 5][해설 X] - 흙길 보수하기 (JAVA)

 

1. 어레이에 넣고 sort 정렬 -> pq로 정렬해서 넣기

• pq 로 하면 인덱스 신경 안써도 되니 코드가 훨씬 직관적인 것 같다.

2. 판자 시작점 갱신: 이전 판자로 갱신된 판자의 시작점이랑, 판자 자체의 시작점 중 더 큰 값으로 갱신해서 사용

• 이전 코드는 시작점 갱신없이 length부터 구했어서 예외케이스에 대처가 안됐나보다.

3. 문제의 핵심 파악하기: 결국 최소 널빤지 사용이기 때문에 널빤지 길이는 최대라고 놓고 시작점 갱신을 해준다.

• 조건이 간단해져서 if문 대신 삼항연산자 사용으로 코드를 간결하게 할 수 있다.

4. 매우 중요한 예외 케이스 찾기: 최대 길이 널빤지를 놓았을 때 다음 웅덩이가 덮인 경우가 있을 수 있다. 때문에 while문 앞에 curr.end < start 인지 확인하는 조건문을 써준다.

import java.util.*;

class Pair {
    int start, end;

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int l = sc.nextInt();

        // 입력 순서 정렬
        PriorityQueue<Pair> puddle = new PriorityQueue<>((a,b)-> (a.start - b.start));

        for (int i = 0; i < n; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();
            puddle.add(new Pair(start, end));
        }

        int start = 0;
        int result = 0;

        while(!puddle.isEmpty()){

            Pair curr = puddle.poll();

            if (curr.end < start) {
                continue;
            }
            start = Math.max(curr.start, start);
            int length = curr.end - start;

            int count = length % l != 0 ? length/l + 1 : length/l;

            result += count;

            start += count*l;

        }

        System.out.println(result);
    }
}

아악 .. 난 언제 느냐 ㅠㅠ