[백준🥇3] #13904 과제 (Python)

https://www.acmicpc.net/problem/13904

13904번: 과제

 

문제

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

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

입력

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

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

출력

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

예제 입력 1

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

예제 출력 1

185

 

✔️ Code 

import sys
input = sys.stdin.readline

n = int(input())
hw = []
checked = [False] * 1001 #주의.. n까지라고 하면 안됨

for _ in range(n):
    d, w = map(int, input().split())
    hw.append((d, w))

hw = sorted(hw, key = lambda x: (x[1], x[0]), reverse=True)

result = 0
for i in range(n):
    d = hw[i][0]
    w = hw[i][1]
    for j in range(d-1,-1,-1):
        if not checked[j]:
            checked[j] = True
            result += w
            break

print(result)

✏️ Comment

아이디어를 모르겠어서 구글링으로 아이디어만 참고하고 이해하면서 구현해봤다. 우선 그리디 유형 문제로, 점수가 높은 것부터 내림차순 정렬해준다. 그리고 최대한 마감일에 맞추어서 과제를 제출하는 식으로 구현하면 된다.

예시의 경우 (4, 60) (2, 50) (4, 40) (3, 30) (1, 20) (4, 10) (6, 5) 인데 첫번째 (4, 60)에서 최대한 day 4에 맞추어서 과제를 내는 것이다. 그런 다음 (2, 50)은 마찬가지로 day 2에 제출한다. (4, 40)은 day 4엔 이미 다른 것을 제출하기로 되어 있으므로 day 3에 제출하고, (3, 30)은 day 1, (6, 5)는 day 6에 마지막으로 제출한다.

위의 루트 대로면 day 1 = 30, day 2 = 50, day 3 = 40, day 4 = 60, day 5 = x, day 6 = 5 이므로 30 + 50 + 40 + 60 + 5 = 185가 된다.