주어진 작업의 선행 관계가 있을 때, 모든 작업을 완료하는 데에 걸리는 최소 시간을 구하는 문제입니다. 하지만 선행 관계가 너무 예쁘게도 작업의 번호보다 작은 번호의 작업만 선행 관계로 주어집니다. 이 조건 때문에 굳이 위상 정렬을 사용하지 않아도 됩니다! DP를 사용해서도 풀 수 있습니다. 그 방법은 아래와 같습니다.
1번부터 n번 작업까지 순서대로 각 작업이 완료되는 데에 걸리는 최소 시간을 dp 배열에 저장합니다. 즉, bottom-up 방식을 사용합니다. 그리고 선행 관계에 대해서는 이미 작은 번호의 작업에 대한 최소 시간을 저장해놓았으니 dp 배열을 참조하여 빠르게 구할 수 있습니다. 이제 각 작업에 대한 최소 시간 중 가장 큰 값을 찾아 출력하면 됩니다.
PS알못 OrbitHv의 PS