[백준/구현] 13904: 과제 - 파이썬

문제

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

13904번: 과제

 

풀이

처음에는 1일차부터 마지막일수까지 각 날짜마다 점수가 큰 과제를 해결하는 문제인줄 알았는데 접근을 잘못하였고

고민을 오래하여도 답을 찾을 수 없어서 블로그를 통해 아이디어를 얻었다.

(여기서 얻었다: https://chinpa.tistory.com/34)

 

마지막 일수부터 1일차까지 해당 날짜에 수행할 수 있는 가장 높은 과제를 해결하면 된다. 

6일차 => [6, 5]

5일차 => X

4일차 => [4, 60], [4, 40], [4, 10]

3일차 => [4, 40], [4, 10], [3, 30]

2일차 => [4, 10], [3, 30], [2, 50]

1일차 => [4, 10], [3, 30], [1, 20]

 

import sys
input = sys.stdin.readline

n = int(input()) # 과제수 입력
hw = [list(map(int, input().split())) for _ in range(n)] # 과제기한, 점수 입력

hw.sort() # 일수가 가장 큰 순서대로 정렬함
canHW = [] # 해당 일수에 가능한 과제를 저장할 리스트
result = 0

# 마지막 일수부터 가장 처음 일수까지 반복
for date in range(n, 0,-1):
    while hw and hw[-1][0] >= date: # 해당 날짜에 수행할 수 있는 과제점수를 리스트에 저장
        canHW.append(hw.pop()[1])
    # 해당 날짜에 수행할 수 있는 과제가 있다면
    if canHW:
        canHW.sort() # 가장 큰 점수대로 정렬함
        result += canHW.pop() # 가장 큰 점수를 pop연산 수행 후 결과에 더함
print(result)