[백준] 1911 - 흙길 보수하기

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

1911번: 흙길 보수하기

 

메모하지 않고, 머리로만 문제를 풀기위해 사고하는 내 모습이 문제인거 같아, 앞으로 문제를 읽고, 바로 사고의 흐름을 적으려고 한다.

 

 

사고의 흐름

1 <= N <= 10,000 개의 물웅덩이가 생겼다.

길이가 L(1 ≤ L ≤ 1,000,000)인 널빤지들을 충분히 가지고 있어서, 이들로 다리를 만들어 물웅덩이들을 모두 덮으려고 한다

물웅덩이를 길이가 L인 널빤지로 덮는 상황 ... OK

 

웅덩이를 발견하면, 웅덩이의 크기에 맞게 널빤지를 덮어주면 된다.

웅덩이가 존재하지 않는 곳에 널빤지를 깔지 않으면 된다.

 

(1) 시작지점과 끝지점을 기준으로 정렬을 해준다.

(2) 정렬된 웅덩이를 하나씩 순회하면서, 널빤지를 대준다.

(2-1) 널빤지의 위치가 웅덩이 시작 전인경우, 웅덩이의 시작지점부터 끝지점까지 널빤지를 대준다.

(2-2) 널빤지의 위치가 웅덩이의 시작지점보다 같거나 큰경우, 이전 널빤지와 웅덩이의 겹치는 지점을 제거하고 널빤지의 갯수를 구해준다.

(2-3) 널빤지의 위치가 이미 웅덩이보다 크거나 같은경우 continue로 넘어가준다.

 

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    public static int N;
    public static int L;
    public static List<Puddle> puddles;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer stk = new StringTokenizer(br.readLine());

        N = Integer.parseInt(stk.nextToken());
        L = Integer.parseInt(stk.nextToken());
        puddles = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            stk = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(stk.nextToken());
            int end = Integer.parseInt(stk.nextToken());
            puddles.add(new Puddle(start, end));
        }

        Collections.sort(puddles, new Comparator<Puddle>() {
            @Override
            public int compare(Puddle o1, Puddle o2) {

                if (o1.start == o2.start) {
                    return o1.end - o2.end;
                }

                return o1.start - o2.start;
            }
        });

        int res = 0;
        int count = 0;
        int idx = 0; // 널빤지 끝부분의 위치
        for (int i = 0; i < N; i++) {
            Puddle cur = puddles.get(i);
            int start = cur.start;
            int end = cur.end;

            if (end <= idx) {
                continue; // 이미 다 채운 경우
            }
            if (idx < start) { // 웅덩이 시작전
                count = ((end - start) / L) + ((end - start) % L > 0 ? 1 : 0);
                idx = start + count * L;
            } else { // 웅덩이가 전 널빤지에 겹치는 경우 - 겹치는 부분제거
                count = ((end - idx) / L) + ((end - idx) % L > 0 ? 1 : 0);
                idx = idx + count * L;
            }

            res += count;
        }

        System.out.println(res);
    }

    public static class Puddle {
        int start;
        int end;

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