[백준 - 1516] 게임 개발

어떤 건물을 짓기 전에 여러 선행 건물이 필요할 수 있고, 선행 건물은 동시에 지을 수 있다. 그래서 총 시간은 선행 시간의 합이 아니라 선행 건물 완료 시간 중 최댓값 + 내 건설 시간이다.

finish(building) = buildTime(building)
                  + max(finish(prerequisite))

재귀로 선행 건물을 먼저 계산하고, 이미 구한 건물은 dp에 저장해 다시 계산하지 않았다. 의존성 그래프를 따라가지만, 각 노드의 최종 완료 시간을 남긴다는 점에서 DP로 볼 수 있다.

문제: 1516 게임 개발 · 코드: GitHub에서 보기