백준 1516번 게임 개발

< 백준 1516번 게임 개발 - 마포 코딩박 >

사용한 알고리즘: DP

 N개의 건물들에 대해, 해당 건물이 지어지는 시간과, 그 건물을 짓기 위해 먼저 지어져야할 건물들의 정보가 입력으로 주어집니다. 각 건물들이 완성되는데까지 필요한 최소 시간을 구하는 문제입니다.
 사실 위상정렬로 풀리는 문제이지만, 저는 DP로 풀었습니다.

문제풀이는 다음과 같습니다.

(1) (코드 10~11)
 'dp[x] : x 를 완공시키는데까지 필요한 최소 시간' 이라고 설정했습니다.

(2) (코드 13~25)
 dp 를 계산하는 함수를 만들어 주었습니다.
 a 라는 건물을 완공시키기 위한 최소 시간은, ( a 건물을 짓는 시간 + a 건물 이전에 지어져야 할 건물들의 완공시간 중 최대값 ) 입니다.