[DP] Python - 1516번, 게임 개발

www.acmicpc.net/problem/1516

import sys

input = sys.stdin.readline

N = int(input())
buildTimes = [-1 for _ in range(N+1)]
prevBuild = {i: [] for i in range(N+1)}
realBuildTimes = [-1 for _ in range(N+1)]


def getBuildTime(index):
    global realBuildTimes
    RET = buildTimes[index]
    for cur in prevBuild[index]:
        if realBuildTimes[cur] != -1:
            RET = max(RET, buildTimes[index]+realBuildTimes[cur])
        else:
            RET = max(RET, buildTimes[index]+getBuildTime(cur))
    realBuildTimes[index] = RET
    return RET


for i in range(N):
    curNums = list(map(int, input().split()))
    buildTimes[i+1] = curNums[0]
    for j in range(1, len(curNums)-1):
        prevBuild[i+1].append(curNums[j])

for i in range(1, N+1):
    print(getBuildTime(i))

prevBuild[i]에는 'i를 짓기 위해 필요한 건물들'이 배열로 저장됩니다.

getBuildTime()은 '건물을 지을 수 있는 최종 시간'을 구하며 dfs 기능을 수행합니다. 이 함수를 통해 특정 건물을 지을 수 있는 최종 시간을 구하게 되면 그 값을 realBuildTimes[]에 저장합니다. 저장되기 전에는 -1이 디폴트로 들어가있는데, -1이 아닌 경우(이미 시간 구한 건물일 경우)에는 dfs를 수행하지 않고 그 값을 그대로 가져와 사용합니다.

 

getBuildTime을 1 until N 까지 돌려주면 끝입니다.