알고리즘(python)/정렬
[Python]위상정렬 백준 1005
문제 https://www.acmicpc.net/problem/1005 동적계획법을 적용하여 구하는 위상정렬이다.위상 정렬에서 큐에서 값들을 뺄때 진입차수 뿐만 아니라 이전 건물까지 걸리는 시간+이번 건물을 짓는 시간과 이전 DP값을 비교하여 더 오래 걸리는시간으로 갱신해주면된다. 해당 건물이 지어지기위해서는 앞에 지어질 건물들의 걸리는 시간들 중에서 가장 긴 시간에 맞춰주어야 모든 건물을 짓고 해당 건물을 지을 수 있기 때문이다. 1234567891011121314151617181920212223242526272829303132333435import sysfrom collections import deque T=int(sys.stdin.readline()) for _ in range(T): N,K=ma..
2020. 4. 14. 01:11
최근댓글