[백준] 1781번 - 컵라면

1. 문제 요약

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

 

각 문제마다

• 데드라인 (d)
• 컵라면 수 (c)

가 주어진다.

모든 문제는 1시간씩 걸리고,
각 문제는 데드라인 이전에만 풀 수 있다.

→ 목표:
얻을 수 있는 컵라면의 최대 개수

---

2. 처음 접근 (틀린 코드)

처음에는 이런 식으로 접근했다.

heapq.heappush(heap, (dead_line, -cup))

 

• 데드라인 기준으로 정렬하면서
• 같은 데드라인이면 컵라면 많은 것 우선 선택

그리고 하나 선택한 뒤

while heap and curr >= heap[0][0]:
	heapq.heappop(heap)

 

즉,

• 하나 고르면
• 같은 데드라인 이하 문제는 다 버리는 방식

---

3. 왜 틀렸는가?

핵심 문제

같은 데드라인에서도 여러 개 선택할 수 있다

---

 반례

3
2 10
2 9
2 8

 

• 데드라인이 2 → 문제 2개까지 가능

정답은 10 + 9 = 19인 반면, 내 코드는 10을 출력한다.

→ 이유:

• 10 하나 고르고
• 나머지 (9, 8) 전부 삭제

---

4. 핵심 개념 깨달음

이 문제의 해결 전략:

데드라인 d까지는 최대 d개 문제를 풀 수 있다

즉, 데드라인최대 선택 가능 개수

1	1개
2	2개
3	3개

---

5. 올바른 접근

 핵심 아이디어

1. 문제를 데드라인 오름차순 정렬
2. 현재까지 선택한 문제들을 heap에 저장
3. 만약 선택한 문제 개수 > 현재 데드라인:  가장 컵라면 적은 문제 제거

---

6. 정답 코드

import heapq
import sys
input = sys.stdin.readline

n = int(input())
problems = []

for _ in range(n):
    d, c = map(int, input().split())
    problems.append((d, c))

problems.sort()

heap = []

for d, c in problems:
    heapq.heappush(heap, c)
    
    if len(heap) > d:
        heapq.heappop(heap)

print(sum(heap))