과제 [백준 13904] (파이썬)

문제

---

과제 [백준 13904]
https://www.acmicpc.net/problem/13904

풀이

---

이 문제는 처음에 주어진 입력을 어떻게 정렬해야하나 고민을 많이 하게 되는 문제였다.

• 날짜에 대해 오름차순을 하고 힙큐에 과제 점수를 넣어주고 만약 과제를 할 시간이 부족하면 힙큐에서 가장 작은 점수를 포기하고 현재 점수를 넣기
• 점수에 대해 내림차순을 하고 1000일째날까지 할 과제가 있는 지 아는 리스트를 선언하고 해당 날짜에 과제를 할 수 있으면 하게 하기

첫번째 풀이 방법은 점수의 크기만 생각했지, 저 방법으로는 같은 날짜가 계속나오는데 점수 크기만 크다면 계속해서 더해줄 수 있는 반례가 있었다. 날짜에 대해 오름차순을 하고 점수에 대해서는 내림차순을 한 내 실수 였다.

코드

---

import heapq
n = int(input())
assign = [list(map(int, input().split())) for _ in range(n)]
assign.sort(key=lambda x : -x[1])
result = 0
possible = [0] * 1001
for d, w in assign:
    flag = True
    for i in range(d, 0, -1):
        if possible[i] == 0:
            possible[i] = 1
            flag = False
            break
    if flag:
        continue
    result += w
print(result)