[BOJ] 1005번: ACM Craft

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

D[i]를 i번째 건물을 짓기 위해 필요한 시간(이전 테크트리의 건물들까지 고려해서)이라고 할 떄 건물들을 필요 테크트리 대로 topological sort한 이후 D를 채워나가면 됩니다.

문제에 주어진 예시로 생각을 해보면 D[4] = max(D[2], D[3]) + 10 일 것입니다.

즉, 지어져있어야 하는 부속 건물들 중에서 가장 오래 걸리는 것의 시간 + 자기 자신을 짓는데 걸리는 시간을 한 것이 D[i]고 topological sort를 했으니 부속 건물들을 짓는데 걸리는 시간은 전부 잘 저장되어있음이 보장되어있습니다.

https://github.com/encrypted-def/BOJ/blob/master/1005.cpp