백준 - 1911

[Silver I] 흙길 보수하기 - 1911

문제 링크

성능 요약

메모리: 39268 KB, 시간: 852 ms

분류

정렬, 스위핑

문제 설명

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

입력

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

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

출력

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

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(); // 널빤지 길이
        int minPlank = 0; // 널빤지들의 최소 개수
        int x = 0; // 이전에 놓은 널빤지의 끝 위치
        int[][] puddle = new int[n][2]; // 물웅덩이의 시작 위치와 끝 위치를 저장하는 배열

        // 물웅덩이 시작 위치와 끝 위치 입력 받기
        for (int i = 0; i < n; i++) {
            puddle[i][0] = sc.nextInt();
            puddle[i][1] = sc.nextInt();
        }

        // 물웅덩이 시작 위치를 기준으로 오름차순 정렬
        Arrays.sort(puddle, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return Integer.compare(o1[1], o2[1]);
                }
                return Integer.compare(o1[0], o2[0]);
            }
        });

        // 각 물웅덩이를 덮기 위해 필요한 널빤지 개수 계산
        for (int i = 0; i < n; i++) {
            if (puddle[i][0] > x) { // 시작위치가 범위보다 클 경우
                x = puddle[i][0];
            }
            if (puddle[i][1] >= x) { // 끝위치가 범위보다 클 경우
                while (puddle[i][1] > x) {
                    x += l;
                    minPlank++;
                }
            }
        }

        System.out.println(minPlank);
    }
}