[백준] [Python] #13904 과제

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

13904번: 과제

처음 읽어봤을 땐 문제가 짧아서 금방 풀수 있을 줄 알았건만,, 문제 읽고 한 10분은 뭐라하는 건지 감도 안왔다.

 

앞에서부터 찾아보면, 해당 일에 마감이 지나지 않은 과제 중 점수를 가장 큰걸 골라도 답이 아니다.

인간 지능으로도 케이스를 못잡겠는데 내가 로직이 구현이 가능할까 싶어 힌트를 역으로 찾아가기로 했다.

주어진 힌트를 보면, 30+50+40+60+5 라서 185라는 것을 알 수 있다.

하나씩 손으로 그려가며 케이스를 찾아본 결과, 뒤에서 부터 진행해야 총합이 최대인 케이스를 구할 수 있었다.

 

1. 주어진 input을 마감일과 점수를 다 계산해야하니 tuple로 list에 저장하고

2. 뒤에서부터 날짜순으로 탐색해야하니 sort로 순서정렬을 한다

3. 마감일이 같은 것 (뒤에서 부터 탐색하는 것이니, 마감일이 임박한 것)을 묶어서 그 중에서 점수가 최대인 것을 고른다

4. list를 다 순회하면서 최대값들을 모아모아 최종 return 한다

 

최종 답안

import sys
sys.stdin = open("input.txt", "r")

n = int(input())
list = []
today = 0
possible = []
ans = 0

for _ in range(0,n):
    d,w = map(int, input().split())
    list.append((d,w))
list.sort() #남은날짜기준 [(1, 20), (2, 50), (3, 30), (4, 10), (4, 40), (4, 60), (6, 5)]
today = list[-1][0] #6

while True:
    if today == 0 :
        break
    while list and list[-1][0]==today:
        possible.append(list.pop()[1])
    today -= 1
    possible.sort()
    if possible:
        ans += possible.pop()
    else: 
        ans += 0
        
print(ans)