[백준] 1911 흙길 보수하기 (JAVA)

문제 링크: 1911번: 흙길 보수하기

 

 

난이도: 골드 5

 

 

소요시간: 1시간

 

 

문제:

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

 

 

입력:

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

 

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

 

 

출력:

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

 

 

문제이해:

이 문제는 웅덩이 개수와 널빤지 길이가 주어지며,

웅덩이 개수만큼 웅덩이 길이가 입력된다. 

 

예제입력 1을 예를 들어보자

3 3
1 6
13 17
8 12

즉 1~6까지 , 13~17까지, 8~12 까지 웅덩이로 덮혀있으며

길이가 3인 널빤지를 최소로 사용하여 이 웅덩이를 덮을때,

널빤지 최소 개수를 구하는 문제이다.

 

이는 다음과 같이 덮혀진다.

 

 

구현 방향:

이 문제는 라인 스위핑 문제이다.

그 이유는 웅덩이를 이벤트라 했을때 이벤트만 발생하는 곳을 탐색하는 것이며

전체 좌표를 훑는게 아니다.

 

즉 예제 입력 1같은 경우는 1~6,  8~12, 13~17부분만 검사를시행하여 널빤지를 배치하면 된다.

해당 부분만 시행하기 위해서 작성자는 우선순위 큐를 사용하여 시작점을 기준으로 오름차순 정렬을 하였다.

 

큐에 대해 하나씩 꺼내면서 널빤지를 배치하며 큐가 빌때까지 반복하면 수행할 수 있다.

 

 

정답 코드:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int N, L; // 널빤지 최소 개수 구할 때 쓸 변수
    static PriorityQueue<int[]> pq = new PriorityQueue<>(
            Comparator.comparingInt(o -> o[0]) // 시작점 기준 오름차순
    );

    public static int solve() {
        int result = 0;
        int covered = 0; // 지금까지 널빤지로 덮은 끝 위치

        while (!pq.isEmpty()) {
            int[] arr = pq.poll();
            int start = arr[0];
            int end = arr[1];

            // 이미 덮은 위치보다 앞에서 웅덩이가 시작하면, 덮은 위치를 웅덩이 시작점까지 당겨줌
            if (covered < start) {
                covered = start;
            }

            // 아직 웅덩이 끝까지 못 덮었으면 널빤지를 계속 깔아줌
            while (covered < end) {
                covered += L; // 널빤지 하나 깔면 L만큼 더 덮임
                result++;
            }
        }

        return result;
    }

    public static void main(String[] args) throws IOException {
        // 초기 세팅
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());

        for (int i = 0; i < N; i++) {
            int start, end;
            st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken());
            end = Integer.parseInt(st.nextToken());
            pq.add(new int[]{start, end});
        }
        //초기세팅 끝

        //탐색 시작
        int result = solve();

        //결과 출력
        System.out.println(result);
    }
}

 

 

마무리하며:

라인 스위핑은 구현 자체는 단순하지만,
어떤 문제에서 이 기법을 떠올려야 하는지 판단하는 과정이 훨씬 더 중요하다.

 

따라서 더 많은 문제를 풀며 연습해야 한다고 생각한다.

 

 

감사합니다。