[BOJ] 13904 과제

문제

웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

입력

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

풀이

먼저 여기서 그리디를 적용할 수 있는 요소는

1. 현재 남은 과제 중에서 제일 점수가 큰 과제를 골라야 한다.

2. 점수가 가장 큰 과제 중에는 마감일에 가장 가까운 과제를 골라야 한다.

그래서 생각해낸 방법은 날짜를 배열로 선언하고(ans) 각 날짜에 과제를 해냈을 때 얻는 점수를 할당하는 것이었다. 만약 요소가 0이 아니면 거기는 그 날은 이미 소모한 것이므로 다른 과제를 넣을 수 없다. 먼저 정렬한 점수 배열을 앞에서부터 스캔하면서 마감일(task[i][1]-1)부터 시작하며 역순으로 스캔하며 빈 자리가 있으면 넣어주는 식으로 구현하였다.

import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
task = []
for _ in range(n):
  d, w = map(int, input().split())
  task.append([d, w])
task.sort(key = lambda x: x[1], reverse = True)
ans = [0] * (n+1)
for i in range(n):
  for j in range(task[i][0]-1, -1, -1):
    if j >= n:
      continue
    else:
      if ans[j] == 0:
        ans[j] = task[i][1]
        break
print(sum(ans))

느낀 점

그리디 문제 특징은 그리디한 사고를 생각해내기가 어렵지만 알고 나면 정말 간단해서 현타가 오게 된다는... 이 문제 또한 머리 속에 대충 로직은 생각이 났지만 구현해내는데 정말 애먹은 케이스인 것 같다. 처음에는 heap을 사용하여 점수가 큰 순, 마감일이 가까운 순으로 정렬하여 풀려고 했지만 정답이 나오지 않았고, 그 다음에는 tmp라는 배열을 선언하여 만약 현재 tmp에 있는 요소의 수 + 이미 정답 배열에 넣은 요소의 개수가 만약 task[i][0]보다 크면 tmp에 넣어주고 0이 되면 정답 배열에 append해주는 식으로 구현했다가(설명하다 보니 복잡하고 이해하기 어렵게 쓴 것 같다. 어차피 틀린 방법이니 개의치 않길 바란다) 문제가 생겨서 좌절했기도 했다. 현재 방법을 생각한 이후에도 런타임 에러(인덱스 에러)가 나와서 심적으로 굉장히 힘들기도 하였다. 여러분도 문제 풀 때 task[i][0](마감일)이 n보다 큰 경우가 나올 수 있다는 경우를 고려하길 바란다.