1911번 : 흙길 보수하기

https://www.acmicpc.net/problem/1911

1911번: 흙길 보수하기

 

문제

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

 

입력

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

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

 

출력

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

 

---

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 웅덩이 개수
        int l = Integer.parseInt(st.nextToken()); // 웅덩이 길이

        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        int result = 0;
        int pre = -1; // 이전 널빤지 위치
        for (int i = 0; i < arr.length; i++) {
            // 이전 널빤지 위치가 현재 웅덩이를 침범하는 경우
            if(pre >= arr[i][0]) {
                // 이전 널빤지 위치가 현재 웅덩이를 덮는 경우
                if (pre >= arr[i][1] - 1) continue;
                int len = arr[i][1] - pre - 1; // 필요한 널빤지의 길이 (시작위치는 덮어져 있으니까 -1)
                if (len % l != 0) {
                    pre = pre + (len / l) * l + l;
                    result += len / l + 1;
                } else {
                    pre = arr[i][1];
                    result += len / l;
                }
            }
            else {
                int len = arr[i][1] - arr[i][0]; // 필요한 널빤지의 길이
                if (len % l != 0) {
                    pre = arr[i][0] + (len / l) * l + l - 1; // 시작 위치부터 덮으니까 -1
                    result += len / l + 1;
                } else {
                    pre = arr[i][1];
                    result += len / l;
                }
            }
        }

        System.out.println(result);
    }
}

 

해결방법

단순히 이전 널빤지의 위치를 보고 아래 두 가지 경우로 나누어 문제를 해결하였다.

1. 이전 널빤지 위치가 현재 웅덩이를 침범하는 경우

2. 이전 널빤지 위치가 현재 웅덩이를 침범하지 않는 경우