[python] 백준 13904번: 과제

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

13904번: 과제

 

# 참고블로그
https://whitehairhan.tistory.com/337

https://velog.io/@heyksw/Python-%EB%B0%B1%EC%A4%80-gold-13904-%EA%B3%BC%EC%A0%9C

문제가 처음 읽었을 때 쉽게 이해가 되지 않았다.
그래서 블로그를 참고하면서 풀었다.
결론적으로 뒤에서 부터 가능한 과제를 그리디 방법으로 풀면 되는 문제였다. 이 문제의 경우 푸는 방법이 그리디말고도 우선순위 큐로 푸는 방법이 있다. 그러나 우선순위 큐의 풀이를 보고도 쉽게 이해가 되지 않았다.
우선순위 큐로 푸는 문제를 많이 접해봐야겠다는 생각을 했다.

 

import sys
sys.stdin = open("BOJ\\greedy\\input5.txt",'r')
input = sys.stdin.readline
array = []
# 문제에서 n<= 1000이기 때문
visit = [False] * 1001
 
# 갯수 받기
n = int(input())
 
for i in range(n):
    d, s = map(int,input().split())
    array.append((d,s))
array.sort(key = lambda x : x[1], reverse =True)
 
answer = 0
 
for day, score in array:
    # 각 점수마다 내림차순 했으므로 그 날짜 값에 해당 되는 값을 우선적으로 넣음
    i = day
    while i > 0 and visit[i]:
        i -= 1
    # 해당되는값 없으면 패스
    if i == 0:
        continue
    else:
        visit[i] = True
        answer += score
print(answer)