[백준 - 1911][GOLD 5][해설 X] - 흙길 보수하기 (JAVA)

문제 링크

---

https://www.acmicpc.net/problem/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());
		
        //웅덩이 시작 위치가 앞선 순서로 정렬
        PriorityQueue<Hole> pq = new PriorityQueue<>((a,b)->(a.start - b.start));
		
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            pq.add(new Hole(start, end));
        }

        int start = 0;
        int total = 0;
	
        while(!pq.isEmpty()){
            Hole curr = pq.poll();

            //이미 판자로 웅덩이를 덮힌 경우면 무시
            if(curr.end < start){
                continue;
            }
			
            //판자 시작점 구하기
            start = Math.max(curr.start,start);
            //세워야하는 최소 판자 길이
            int length = curr.end - start;
			
            //판자 개수 구하기
            int count = length % L != 0 ? length/L + 1 : length/L;
			
            //판자 개수 더하기
            total +=count;
            //다음 판자 최소 시작점 갱신 
            start += count*L;
        }

        System.out.println(total);
    }
}

class Hole{
    int start;
    int end;

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

 

 

실행 결과

---

 

팁

---

• 가장 효율적으로 판자를 세우는 방법이 어떤것이 있을지 생각해야한다.