Solution
그리디 문제를 풀 때는 여러가지 방법으로 데이터를 정렬해보고 생각하면 좋다.
문제를 풀기전에, 다이나믹 프로그래밍으로 풀 건지, 그리디로 풀 건지 먼저 판단해야된다. 전에 공부했을 때 이 두 알고리즘을 구분하는 기준은, 데이터를 가지고 순서대로 판단을 해볼 때 지금 이 데이터를 포기함으로써 나중에 이득을 보게 될 수 있는가 라고 정리했었다. 이 문제의 경우에는 일단은 무조건 좋은 점수를 먹는게 중요하기 때문에 다이나믹 프로그래밍보다는 그리디가 어울린다.
그리디라고 방향을 잡았기 때문에, 날짜를 기준으로도 정렬해보고 점수로도 정렬을 해봤다. 잘 생각해보면, 점수로 정렬하는게 맞다.
점수로 내림차순 정렬을 하되, 그 과제를 최대한 나중에 수행하는 쪽으로 구현한다. 예를 들어, (1, 20), (2, 30), (2, 10), (3, 40), (3, 35) 의 과제 데이터가 있을 때, 일단은 제일 점수 높은 (3, 40)을 수행할 생각을 한다. 단, 이 과제를 day = 3 일차에 수행한다고 생각하면서 먹는다. 그래야 day = 1, 2 일차에 먹을 수 있는 과제의 수가 많아지기 때문이다. 만약에 그 과제를 day = 1 일차에 수행한다 치면 day = 1인 과제는 더 이상 먹을 수 없게 되기 때문이다. 그리고 나서는 2번째로 점수가 높은 (3, 35) 를 선택한다. 하지만 이미 day = 3 일차에는 수행할 과제를 확보해놨기 때문에 그 전인 day = 2 일차에 이 과제를 수행하기로 한다.
이런 흐름으로 문제를 풀었더니 정답 처리를 받을 수 있었다. 아래 코드에서 (visit[x] = True) 는 x 일에 과제하기로 처리가 완료 되었다는 뜻이다.
Code
import sys
n = int(input())
homework =[]
visited = [0] * 1001
for _ in range(n):
d,w = map(int,input().split())
homework.append([d,w])
homework.sort(key=lambda x : x[1],reverse=True)
answer =0
for day, worth in homework:
i = day
# 과제를 할 날짜 탐색
while i > 0 and visited[i]:
i -= 1
# 과제를 할 날짜가 없으면 패스
if i == 0:
continue
else:
visited[i] = True # 과제 완료
answer += worth # 점수를 더해준다.
print(answer)
