[백준] 1781. 컵라면 (Java)

 

🔒 문제

1781번: 컵라면

 

 

🔑 알고리즘

우선순위 큐, 그리디 알고리즘

 

 

💡  풀이

N이 최대 20만이므로 시간 복잡도가 O(NlogN)을 넘어가면 시간 초과가 날 것이다.

따라서 순열 등 시간 복잡도가 높은 방법을 사용할 수 없다.

 

 

1. 현재 단위 시간과 데드라인이 동일한 문제 중 최대 문제 풀기

문제 번호	1	2	3	4
데드라인	1	1	2	2
컵라면 수	6	7	100	100

 

해당 방법으로는 위와 같은 상황에서 1,2번 문제를 풀게 되므로 컵라면을 최대로 획득할 수 없다

위 상황에서는 1,2 번 문제를 포기하고 3,4번 문제를 풀어야 컵라면을 최대로 받을 수 있다.

 

 

 

2. 컵라면 수가 높은 문제부터 풀기

문제 번호	1	2	3	4
데드라인	1	1	3	3
컵라면 수	6	7	100	100

 

해당 방법으로는 위와 같은 상황에서 1일차에 3번, 2일차에 4번 문제를 풀고 3일차에는 풀 수 있는 문제가 없으므로 100, 100으로 200개의 컵라면만 획득한다.

하지만 3,4번 문제의 데드라인이 여유롭기 때문에 2번 문제를 먼저 풀어서

7, 100, 100으로 207 개의 컵라면을 획득할 수 있는데 우선 순위에 의해 데드라인이 짧은 다른 문제를 놓치게 된다.

 

 

 

3. 마지막 단위 시간부터 접근

 

마지막 단위 시간부터 하나씩 단위 시간을 감소시키며 계산하면

이미 데드라인이 지난 나머지 문제들을 고려하지 않아도 되므로 선택에 영향을 받지 않는다.

 

문제 예시로 예를 들면

단위 시간 6에는 이미 다른 문제들은 데드라인이 지나 선택지가 문제 7밖에 없다.

단위 시간 5, 4에는 데드라인이 지나지 않은 문제가 없고

단위 시간 3에는 3,4번 문제 중 컵라면 수가 높은 3번 문제를 푼다.

단위 시간 2에는 4, 5, 6 번 문제 중 컵라면 수가 높은 6번 문제를 푼다.

단위 시간 1에는 1, 2, 4, 5 번 문제 중 2번을 푼다.

따라서 순서대로 2,6,3,7 문제를 풀고 컵라면을 최대로 받을 수 있다.

 

이를 위해 과제가 정렬되어야 하고, 푼 문제는 해결 가능한 문제 리스트에서 제거해야 하므로 우선순위 큐를 사용하였다.

*이때 전체 과제 큐는 데드라인을 기준으로 내림차순 정렬해야 현재 단위 시간에 맞춰서 꺼낼 수 있고

해결 가능한 과제 큐는 점수를 기준으로 내림차순 정렬해야 가장 점수가 높은 과제를 꺼낼 수 있다.

PriorityQueue<Problem> problems = new PriorityQueue<>((p1, p2) -> -(p1.deadline - p2.deadline));
PriorityQueue<Problem> availProblems = new PriorityQueue<>((p1, p2) -> -(p1.score - p2.score));

 

 

✏️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		PriorityQueue<Problem> problems = new PriorityQueue<>((p1, p2) -> -(p1.deadline - p2.deadline));
		PriorityQueue<Problem> availProblems = new PriorityQueue<>((p1, p2) -> -(p1.score - p2.score));

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int deadline = Integer.parseInt(st.nextToken());
			int score = Integer.parseInt(st.nextToken());

			problems.add(new Problem(deadline, score));
		}

		int time = problems.peek().deadline;
		int ans = 0;
		for (int i = time; i >= 1; i--) {
			
			// 데드라인에 맞는 문제들 큐에 삽입
			while(!problems.isEmpty()) {
				if(problems.peek().deadline == i) {
					availProblems.add(problems.poll());
				} else
					break;
			}
			
			// 풀 수 있는 문제가 있다면 그 중 가장 점수가 높은 문제 풀기
			if(!availProblems.isEmpty()) {
				ans += availProblems.poll().score;	
			}
			
		}
		
		System.out.println(ans);
	}

	static class Problem {
		int deadline, score;

		public Problem(int deadline, int score) {
			this.deadline = deadline;
			this.score = score;
		}
	}
}