백준 - 흙길 보수하기 (1911) : JAVA

문제 유형
그리디

풀이 방법 도출

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

well known 그리디 문제입니다.

규칙을 찾아야하는데, 제가 찾은 규칙은 다음과 같습니다.

"오름차순으로 정렬해서 물웅덩이의 시작(start)과 끝(end)이 작은 웅덩이부터 널빤지로 덮는다."

이러한 규칙의 근거는 다음과 같습니다.

"앞의 물 웅덩이부터 널빤지로 덮으면 뒤에 있는 물 웅덩이를 덮어줄 수 있다."
"뒤에 있는 물 웅덩이부터 덮으면 앞 물 웅덩이를 덮을 수 없다."

list.sort((n1, n2) - > {
    if (n1.start != n2.start) return n1.start - n2.start;
    return n1.end - n2.end;
});

먼저 정렬을 통해 start를 기준으로 오름차순 한 후에, 같다면 end를 기준으로 오름차순으로 정렬합니다.

for (int i = 1; i < list.size(); i++) {
    Node cur = list.get(i);

    if (cur.end <= right) continue;

    cur.start = Math.max(cur.start, right);


    if (cur.getLen() % l == 0) {
        answer += (cur.getLen() / l);
        right = cur.start + (cur.getLen() / l) * l;
    } else {
        answer += (cur.getLen() / l + 1);
        right = cur.start + (cur.getLen() / l + 1) * l;
    }

}

이후 위와 같이 널빤지의 길이로 나눠서 최적의 해를 구합니다.

시간 복잡도
O(N)

코드

package test;

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

class Node {
	int start;
	int end;
	int len;
	
	Node (int start, int end) {
		this.start = start;
		this.end = end;
	}
	
	int getLen() {
		return this.end - this.start;
	}
}

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());
		
		List<Node> list = new ArrayList<>();
		
		for (int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			
			list.add(new Node(start, end));
		}
		
		int right = 0;
		int answer = 0;
	
		list.sort((n1,n2)-> {
			if (n1.start != n2.start) return n1.start - n2.start;
			return n1.end - n2.end;
		});
		
		Node first = list.get(0);
		
	
		if (first.getLen() % l == 0) {
			answer += (first.getLen() / l);
			right = first.start + (first.getLen() / l) * l;
		}
		else {
			answer += (first.getLen() / l + 1);
			right = first.start + (first.getLen() / l + 1) * l;
		}
		
		
		for (int i=1; i<list.size(); i++) {
			Node cur = list.get(i);
			
			if (cur.end <= right) continue;
			
			cur.start = Math.max(cur.start, right);
			
			
			if (cur.getLen() % l == 0) {
				answer += (cur.getLen() / l);
				right = cur.start + (cur.getLen() / l) * l;
			}
			else {
				answer += (cur.getLen() / l + 1);
				right = cur.start + (cur.getLen() / l + 1) * l;
			}

		}
		
		System.out.println(answer);
		
	}
	
	
}