BOJ 1005 - ACM Craft

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

문제에서 주어지는 테크트리대로 문제 예제와 비슷하게 그래프를 그려보면 DAG 형태가 된다. 이 문제는 DAG(directed acyclic graph, 사이클이 없는 방향 그래프)에서 가장 긴 경로의 길이를 구하는 문제인데, 다이나믹 프로그래밍으로 풀 수 있다.

T[i] = i 번째 건물이 지어지기 위해 게임시작부터 걸리는 최소 시간이라고 하자. 최소 시간이라고 했지만, 사실 T[i]는 i번째 건물에서 끝나는 가장 긴 경로의 길이이다..

C[i] = i 번째 건물'만'을 짓는데 걸리는 시간이라고 하자. T[i]는 i번째 건물을 짓기 위해 지어야하는 선행 건물 j들의 T[j] + C[i]의 최대값이 된다.

이런 종류의 문제를 반복적 DP로 풀려고 하면, 상태의 의존 관계에 따라 테이블의 계산 순서를 정해줘야 한다. 이 문제의 경우는 그래프를 위상정렬 한 순서대로 테이블을 채워주면 된다. (재귀로 풀면 의존관계를 고려하지 않아도 돼서, 훨씬 속편합니다.)

코드 :
http://ideone.com/tR0Wb1

비슷한 문제 :
https://www.acmicpc.net/problem/1948
http://codeforces.com/problemset/problem/615/B
https://www.acmicpc.net/problem/2631