백준 1005 ACM Craft

먼저 주어진 건설 순서를 이용해서 그래프를 만들고, 지어야 할 건물 W부터 시작해서 거꾸로 탐색하는 방식으로 dp로 구현해 볼 생각이다.

거꾸로 탐색하면서 건물 W를 짓기 전에 지어야 할 각 건물까지의 시간 중 최대값을 선택하는 방식으로 하면 될 것 같다. 그리고 이미 탐색한 부분은 메모이제이션을 통해 더 탐색하지 않도록 한다.

위상정렬 문제를 예전에 푼 것을 좀 찾아봐서 다시 풀어봐야겠다.
이 문제는 그냥 그래프 + dp처럼 풀어서 AC를 받았는데, 예전에 풀었던 문제 중에 경로까지 출력해야 하는 문제가 있어서 좀 까다로웠던 것 같고 위상정렬을 풀기 위한 방식이 있었는데... 기억이 잘 안난다. 찾아서 풀어보자!