[백준 13904] 과제 파이썬 문제 풀이

문제 풀이: 해당 문제는 어려워서 다른 사람 블로그를 참고했다.

https://whitehairhan.tistory.com/337

n = int(input())
l = []
for _ in range(n):
    a, b = map(int, input().split())
    l.append((a, b))
l.sort()
d = []
result = 0
for date in range(n, 0, -1):
    while l and l[-1][0] >= date:
        d.append(l.pop()[1])
    if d:
        d.sort()
        result += d.pop()
print(result)

풀이를 해보면 먼저 마감일과 점수를 튜플 형태로 l에 담는다. l을 정렬하면 마감일이 적은 수부터 오름차순으로 정렬한다.

d는 해당 일수에 가능한 과제를 저장하는 리스트이다.

이 문제는 마감일이 큰 것부터 낮은 것까지 반복해 나가는 것이 핵심이다. 따라서 date는 n부터 1까지 거꾸로 진행해나가야 한다. (date를 1부터 반복하는 것은 최적의 해를 구할 수 없다.)

정렬된 l은 (1, 20), (2, 50), (3, 30), (4, 10), (4, 40), (4, 60), (6, 5) 다음과 같이 정렬되어 있다.

따라서 현재 l[-1][0]은 6이 된다. 이후에 l.pop()에 의해 l[-1][0]의 값은 변한다.

date가 4인 경우를 보면 d에는 60, 40, 10다음과 같이 정렬되어 있고 d.sort()에 의해 10, 40, 60으로 정렬된다.

d.pop()에 의해 date가 4일 때 받을 수 있는 가장 높은 점수 60이 result에 더해진다.

참고한 블로그에서 캡쳐한 사진

전체적인 과정은 다음과 같이 선택된다.