백준 1781 : 컵라면

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

1781번: 컵라면

[ 문제풀이 ]

처음에는 데드라인이 현재 날짜 기준 이하인 문제들 중 가장 컵라면 개수가 많은 문제를 풀도록 하였다. 하지만 다음과 같은 반례가 존재하게 된다.

7
1 9
1 8
2 200
2 99
3 100
5 999
5 150

 

내가 생각한 방법은 1-9, 2-200, 3-100, 5-999, 5-150을 선택하게 되지만 정답은 2-200, 2-99, 3-100, 5-999, 5-150을 선택하는 것이다.

이는 1일부터 시작하는 것이 아니라 마지막 데드라인 날짜부터 역으로 거슬러 올라간다면 해결할 수 있다.

첫날부터 고려한다면 현재 날짜보다 데드라인이 큰 문제가 더 높은 우선순위를 차지하는 경우가 발생하지만, 마지막 날부터 고려한다면 현재 날짜보다 낮은 데드라인을 가지는 문제는 고려해줄 필요가 없게 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static class Node implements Comparable<Node> {
		int deadLine, cnt;

		public Node(int deadLine, int cnt) {
			this.deadLine = deadLine;
			this.cnt = cnt;
		}

		@Override
		public int compareTo(Node o) {
			return o.cnt - this.cnt;
		}
	}

	static int N;
	static List<Node> nodeList;
	static PriorityQueue<Node> pq;

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))){
			N = Integer.parseInt(br.readLine());
			nodeList = new ArrayList<>();
			for (int i = 1; i <= N; ++i) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int deadLine = Integer.parseInt(st.nextToken());
				int cnt = Integer.parseInt(st.nextToken());
				nodeList.add(new Node(deadLine, cnt));
			}

			Collections.sort(nodeList, (Node a, Node b) -> a.deadLine - b.deadLine);

			bw.write(solve() + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public static int solve() {
		pq = new PriorityQueue<>();
		int totalCnt = 0;
		int idx = nodeList.size() - 1;
		for (int day = nodeList.get(idx).deadLine; day >= 1; --day) {
			for (; idx >= 0; --idx) {
				if (nodeList.get(idx).deadLine < day) break;
				pq.offer(nodeList.get(idx));
			}

			if (pq.isEmpty()) continue;
			totalCnt += pq.poll().cnt;
		}

		return totalCnt;
	}
}