[백준 1781] 컵라면 - JAVA

문제 링크

문제 정의

• $N$개의 문제가 주어지고 단위 시간 $N$이 주어짐
• 문제는 데드라인과 보상(컵라면) 값이 주어짐
• 문제 하나를 풀 때 단위 시간 1이 소요
• 단위 시간 $N$까지 문제를 풀 때 보상으로 받을 수 있는 최대 컵라면 수를 출력

---

접근 방법

1. 핵심 로직: 역순 스케줄링 (Reverse Scheduling)

보통 스케줄링 문제는 $1$일부터 순차적으로 생각하기 쉽지만
이 문제의 핵심은 마지막 날(N일)부터 $1$일까지 거꾸로 검사하는 것입니다.

왜 거꾸로일까요?

1일부터 선택하면
"오늘 이걸 하는 게 맞나? 나중에 더 좋은 게 나오면 어떡하지?"라는 불확실성이 생기지만

마지막 날부터 거꾸로 오면
"이 날짜까지 할 수 있는 모든 과제 중 가장 보상이 큰 것"을 확실하게 선택할 수 있기 때문입니다.

---

2. 두 가지 우선순위 큐(PQ)를 활용한 응용

이전에 프로그래머스 스케줄링 문제를 풀며 익혔던
'두 개의 큐' 전략을 이 문제에 응용했습니다.

첫 번째 큐 (basePq): 과제들을 데드라인이 늦은 순서(내림차순)로 정렬하여 보관합니다. (현재 시점에서 수행 가능한 과제들을 공급하는 역할)

두 번째 큐 (comparePq): 현재 날짜에 수행 가능한 과제들의 보상(reward)을 내림차순으로 정렬합니다. (가장 이득이 큰 과제를 선택하는 역할)

---

3. 알고리즘 흐름 (그리디 전략)

로직은 다음과 같이 간결하게 동작합니다.

1. 전체 기간인 $N$일부터 1일까지 하루씩 감소하며 반복문 수행
2. basePq에서 현재 날짜(currentDeadLine)보다 데드라인이 크거나 같은 과제들을 모두 꺼내 comparePq에 삽입
3. comparePq 중 보상이 가장 큰 것을하나를 골라 결과값에 더합니다.

---

코드

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

class Problem implements Comparable<Problem> {
	int deadline;
	int reward;

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

	@Override
	public int compareTo(Problem o) {
		return o.deadline - this.deadline;
	}
}

public class Main {
	static StringTokenizer st;
	static PriorityQueue<Problem> basePq;
	static int N;
	public static void main(String[] args) throws IOException {
		init();
		System.out.println(greedy());
	}

	static long greedy() {
		long total = 0;
		PriorityQueue<Integer> comparePq = new PriorityQueue<>(Collections.reverseOrder());
		
		for (int currentDeadLine = N; currentDeadLine >= 1; currentDeadLine--) {
			while (!basePq.isEmpty()) {
				if (basePq.peek().deadline < currentDeadLine) break;
				comparePq.offer(basePq.poll().reward);
			}

			if (!comparePq.isEmpty()) total += comparePq.poll();
		}

		return total;
	}

	static void init() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		basePq = new PriorityQueue<>();
		N = Integer.parseInt(br.readLine());

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int d = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());

			basePq.offer(new Problem(d, r));
		}
	}
}