백준 컵라면(1781)

컵라면

1. 힌트

1) 데드라인이 $d$인 문제는 $[1, d]$일에 풀 수 있습니다.

2) 데드라인이 짧은 문제부터 보면서 어떤 문제를 고를지 결정해봅시다. 어떤 문제를 확인하는데 데드라인이 $d$라고 합시다. 그런데 지금 푼 문제의 개수가 $d$개보다 적다면 언제나 그 문제는 풀 수 있습니다.

3) 물론 위에서 고른 문제가 언제나 최적해는 아닙니다. 데드라인이 짧은 문제부터 확인하므로 지금까지 고른 문제들은 언제나 새로운 문제로 교체할 수 있습니다.

2. 접근

1) 비슷한 문제를 풀어본 적이 있던가?

순회강연

범위를 제외하고 완전히 동일한 문제입니다. 순회강연 문제는 $O(N^2)$풀이가 가능하지만 이 문제는 $N$이 최대 $2 \times 10^5$이므로 불가능합니다.

2) 단순한 방법에서 시작할 수 있을까?

언뜻 생각하면 각각의 데드라인 $d$별로 받을 수 있는 컵라면 개수 $v$가 가장 높은 것부터 고르면 될 것 같습니다. 그러나 이 풀이는 문제를 반드시 $d$일에 풀 필요가 없다는 이유 때문에 불가능합니다.

3
3 3
3 2
3 1

이러한 입력이면 $1,\ 2,\ 3$번째 날에 나눠 풀면 모든 문제를 다 풀 수 있습니다.

3) 순서를 강제할 수 있을까?

데드라인이 짧은 문제부터 확인하면서 여유가 있다면 일단 담아봅시다. 물론 잘못된 선택을 할 수도 있겠지만, 기존의 선택을 만회할 수 있습니다.

왜냐하면, 기존에 담았던 문제의 데드라인은 지금 확인하는 문제의 데드라인보다 무조건 같거나 짧으므로 그 문제를 지금 확인하는 문제로 교체할 수 있기 때문입니다. 교체할거면 무조건 가장 컵라면을 적게 주는 문제를 교체하는 것이 좋겠죠. 이 부분은 우선순위 큐를 사용해서 가장 컵라면을 적게 주는 문제를 뽑아낼 수 있도록 합시다.

위에서 여유가 있다면 담는다고 했는데 정확하게 어떤 조건을 말하는 것일까요? 바로 지금까지 담은 문제의 수보다 현재 확인하는 문제의 데드라인이 큰 경우입니다. 담은 문제들을 언제 풀 지는 정해지지 않았지만 $1$일부터 연속해서 푸는 것으로 생각할 수 있습니다. 이렇게 왼쪽으로 전부 밀어버리면 반드시 남는 여유 날짜가 나옵니다. 따라서 무조건 담을 수 있습니다.

3. 구현

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		ArrayList<Pair> S = new ArrayList<>(N);
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int d = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			S.add(new Pair(d, v));
		}
		Collections.sort(S);
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		for (Pair x : S) {
			if (pq.size() < x.deadline) {
				pq.offer(x.value);
			} else if (pq.peek() < x.value) {
				pq.poll(); pq.offer(x.value);
			}
		}
		int sum = 0;
		for (int x : pq) sum += x;
		System.out.println(sum);
	}

}

class Pair implements Comparable<Pair> {
	int deadline, value;
	
	Pair(int d, int v) { deadline = d; value = v; }
	
	@Override
	public int compareTo(Pair o) { return deadline - o.deadline; }
	
}

1) 시간 복잡도

$O(NlgN)$