백준 1911번 - 흙길 보수하기

문제

백준 1911번 - 흙길 보수하기

아이디어

• 앞에서부터 차례대로 덮기 위해 시작 위치를 기준으로 오름차순 정렬한다. 겹치는 웅덩이는 없기 때문에 특별한 조건 없이 정렬하면 된다.
• 최소한의 널빤지를 사용하기 위해서는 길이가 정해진 널빤지로 웅덩이를 덮고 나서 남은 널빤지의 길이를 최대한 활용해야 한다.
• 만약 마지막에 덮은 널빤지의 남은 길이로 다음 웅덩이를 덮을 수 있다면 널빤지 하나를 아낄 수 있다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N log N)

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_1911 {
    public static void main(String[] args) throws IOException {

        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());

        Puddle[] puddles = new Puddle[n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            puddles[i] = new Puddle(s, e);
        }

        Arrays.sort(puddles);

        int count = 0; //필요한 널빤지 개수
        int now = 0;   //마지막 널빤지의 끝

        for (Puddle puddle : puddles) {

            //마지막 널빤지의 끝 >= 웅덩이 시작 위치이면 새로운 널빤지를 사용하지 않아도 된다.
            if (now < puddle.start) {
                now = puddle.start;
            }

            //필요한 만큼 널빤지 사용
            while (now < puddle.end) {
                now += l;
                count++;
            }
        }

        System.out.println(count);
    }

    static class Puddle implements Comparable<Puddle> {

        int start, end;

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

        @Override
        public int compareTo(Puddle o) {
            return this.start - o.start;
        }
    }
}