[python] 백준 - 13904(과제)

골드3 그리디 문제이며, 시간 제한은 1초이다.

문제

해결 과정

처음에 문제를 보고 들었던 생각은 반복문을 사용해서 1부터 마감 기한이 1보다 큰 과제 중 가장 큰 점수를 더해주는 방식이 떠올랐다. 하지만 이 방식은 틀릴 수 밖에 없다. 문제의 예시 입력만 봐도 3일차에 30을 골라야 하기 때문이다. 따라서 입력된 마감 기한과 점수를 마감 기한을 첫 번째 기준, 점수를 두 번째 기준으로 내림차순 정렬한 뒤 거꾸로 탐색했다. 제일 큰 마감 기한 값부터 1까지 내려가며 마감 기한이 이보다 크거나 같은 과제의 점수 중 제일 큰 값으로 설정하고, 같은 값을 계속해서 탐색하지 않기 위해 visited 리스트를 사용해서 막아줬다.

풀이

n = int(input())
arr = []
max_day = 0
for _ in range(n):
  day, score = map(int, input().split())
  max_day = max(max_day, day)
  arr.append((day, score))

sorted_arr = sorted(arr, key=lambda x: (-x[0], -x[1]))
visited = [False for _ in range(n)]
result = 0

idx = -1
for day in range(max_day, 0, -1):
  max_value = 0
  for j in range(n):
    if day <= sorted_arr[j][0] and not visited[j] and max_value < sorted_arr[j][1]:
      max_value = sorted_arr[j][1]
      idx = j
  if max_value > 0:
    visited[idx] = True
    result += max_value
print(result)