[백준] 1781번 : 컵라면

문제

 

 

접근 방식

정말 쉬운데 하고 풀었다가 바로 틀려버린 문제다...

 

데드라인이 빠른 순으로 정렬하고 같다면 보상이 큰 순으로 정렬한 후에

그대로 반복문을 돌면서 더해줬더니 예제는 맞지만 제출하니 틀렸다.

 

예제가 하나뿐이라 생각하지 못한 케이스가 있었는데

데드라인이 나중이라도 이전 데드라인 문제를 생략하고

이후의 데드라인 문제를 푸는 것이 좋을 때가 있다.

2 30
2 20
3 60
3 50

 

위와 같이 데드라인이 2일 때 2개를 선택하는 것보단

둘 다 선택하지 않고 데드라인이 3일 때를 선택하는 것이 더 효율적이다.

 

그래서 정렬은 그대로 유지하되 최소힙을 사용해 이전에 선택한 값이

이후에 선택할 값보다 비효율적인 경우 교체해줘야 한다.

2 30
2 20
최소힙 {20, 30}

3 60
최소힙 {30, 60}

3 50
최소힙 {50, 60}

 

예를 들어, 위와 같이 데드라인이 2인 경우를 모두 최소힙에 넣어둔 후에

데드라인이 3이고 보상이 60일 때는 최소힙에 있는 20과 60을 교체해주면 될 것이고

다음 경우인 데드라인이 3이고 보상이 50인 경우도 30과 50을 교체해주면 된다.

 

 

풀이

public class Main {

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

		int n = Integer.parseInt(br.readLine());
		long max = 0;

		PriorityQueue<Exam> sorted = new PriorityQueue<>(
			(o1, o2) -> o1.d != o2.d ? o1.d - o2.d : -(o1.c - o2.c)
		);

		PriorityQueue<Integer> cup = new PriorityQueue<>();

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			sorted.offer(new Exam(st.nextToken(), st.nextToken()));
		}

		while (!sorted.isEmpty()){
			Exam exam = sorted.poll();

			int size = cup.size();

			if (size < exam.d) {
				cup.offer(exam.c);
				max += exam.c;
			}
			else if (size == exam.d && cup.peek() < exam.c) {
				int prev = cup.poll();
				cup.offer(exam.c);
				max += (exam.c - prev);
			}
		}

		System.out.println(max);
	}

	private static class Exam {
		int d;
		int c;

		public Exam(String d, String c) {
			this.d = Integer.parseInt(d);
			this.c = Integer.parseInt(c);
		}
	}
}