Koala 7주차 : 다익스트라 알고리즘(+ 우선순위 큐)

 

다익스트라 알고리즘을 본격적으로 공부해보기 전에 우선순위 큐에 관련된 문제를 조금 더 풀어보고 시작해보도록 하자

 

 

* 우선순위 큐와 관련된 문제풀이

 

1. 29160 : 나의 FIFA 팀 가치는?

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

 

import sys
input = sys.stdin.readline
from heapq import heappush, heappop

N, K = map(int,input().split())
hq = [[0] for _ in range(12)]
for _ in range(N):
    p, w = map(int,input().split())
    heappush(hq[p],-w)

for _ in range(K):
    for i in range(1,12):
        v = -heappop(hq[i])-1
        v = max(0,v)
        heappush(hq[i],-v)

ans = sum(-hq[i][0] for i in range(1,12))
print(ans)

 

 

 

 

이번주는 갑자기 예상에 없던 해커톤을 나가고, 예상에 있었던 자격증 시험을 보고, 사랑니를 빼게 되어서 겨울 스터디를 하면서 처음으로 문제도 많이 못풀고 진도도 따라가지 못해서 모의테스트를 건너뛰어야했다.

 

다익스트라 알고리즘은 다음주에 자세히 공부해봐야겠다.