항해 99 알고리즘 TIL : 1450 냅색문제

🚀 문제

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

🚀 정답 코드

import heapq
import sys

input = sys.stdin.readline

# 문제 수 입력
N = int(input())

# 각 문제의 (마감일, 컵라면 수)를 리스트로 입력받음
ramens = [tuple(map(int, input().split())) for _ in range(N)]

# 마감일 기준으로 정렬
ramens.sort()

# 전체 데드라인 중 가장 늦은 날 계산
dead_day = max([r[0] for r in ramens])

time = 1         # 현재 시간(1일부터 시작)
index = 0        # ramens 리스트 순회 인덱스
cur_ramens = []  # 현재 시간까지 푼 문제들 (최소 힙 사용)

# 1일부터 데드라인 마지막 날까지 반복
while time <= dead_day:
    # 현재 날짜(time)까지 마감인 문제들을 힙에 추가
    while index < N:
        if ramens[index][0] == time:
            # 컵라면 수를 기준으로 최소 힙 구성
            heapq.heappush(cur_ramens, (ramens[index][1], ramens[index][0]))
            index += 1
        else:
            break

    # 문제 수가 현재 날짜보다 많으면 가장 적은 컵라면 수를 제거
    while len(cur_ramens) > time:
        heapq.heappop(cur_ramens)

    time += 1

# 힙에는 최적 선택된 문제들만 남아있고, 그 문제들의 컵라면 수를 모두 더함
print(sum([r[0] for r in cur_ramens]))

🚀 시행착오 했던 부분

우선 그리디 문제임을 빨리 파악하지 못했다. 부분 문제들이 있고, 같은 데드라인 사이에서 어떤 컵라면을 선택할지 골라야하고, 결국 누적 합을 알아내는 문제라 DP 문제라고 생각했다/

하지만, 현재 고른 컵라면에 따라서 다음 컵라면을 고르는데에 영향을 주지 않기 때문에 현재 상황의 컵라면에서 어떤 컵라면을 남길 것인지에만 집중하면 된다.

따라서 DP 보다는 그리디 문제였고, 거기에 더해서 현재 데드라인에서 컵라면을 가장 많이 남길 수 있도록 적은 컵라면을 빼기 위해 우선 순위 큐를 활용하는 문제였다.