[백준] 1005.ACM Craft - python

https://www.acmicpc.net/problem/1005

 

난이도: 골드 3

알고리즘: DP

 

풀이과정

다음과 같은 상황을 고려해보자.

 

세워야 하는 빌딩이 1번이고 1번 빌딩을 세우기 위해서 2, 3, 4 번 빌딩이 세워져야 한다.

이러한 상황에서 1번 빌딩을 세우는데 드는 시간을 식으로 나타내면 다음과 같다.

 

1번 빌딩을 짓기위한 총 시간 = (1번 빌딩을 세우는 시간) + max(2, 3, 4번 빌딩을 짓기 위한 총 시간)

 

2, 3, 4번 빌딩을 짓기 위한 총 시간은 위 식을 재귀적으로 이용하여 구할 수 있다.

 

여기서 DP를 사용하여 각 빌딩이 을 짓는 데 걸리는 총 시간을 기록하여 시간을 더 줄일 수 있다.

 

소스코드

def solve(target):
    global dp
    if dp[target] != -1:
        return dp[target]
    if len(buildings[target]) == 0:
        dp[target] = times[target]
        return dp[target]
    cur_max = -1
    for building in buildings[target]:
        cur_max = max(cur_max, solve(building))
    dp[target] = times[target] + cur_max
    return dp[target]


T = int(input())
for _ in range(T):
    N, K = map(int, input().split())
    times = list(map(int, input().split()))
    times.insert(0, 0)  # 1번부터 시작하도록
    buildings = [[] for _ in range(N + 1)]
    for i in range(K):
        X, Y = map(int, input().split())
        buildings[Y].append(X)
    target = int(input())
    dp = [-1 for _ in range(N + 1)]
    solve(target)
    print(dp[target])