문제 링크

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

문제 설명

• 건물을 짓는 순서가 주어진다
• 건물을 짓는 시간이 주어진다
• 특정 건물을 짓는데 걸리는 최소 시간 출력

풀이

• 현재 건물을 짓는데 걸리는 최소 시간
  • 현재 건물을 짓는데 반드시 건설되어야 하는 건물들 중 최대 시간 + 현재 건물을 짓는데 걸리는 시간
• bottom-up
• 더 이상 DP 배열이 갱신되지 않을 때까지 반복

코드

import sys


def init():
    n, k = map(int, ipt().split())
    time_list = [0] + list(map(int, ipt().split()))
    prev_list = [[] for _ in range(n+1)]
    for _ in range(k):
        x, y = map(int, ipt().split())
        prev_list[y].append(x)
    w = int(ipt())
    dp = [float('inf')] * (n+1)
    for i in range(1, n+1):
        if not prev_list[i]:
            dp[i] = time_list[i]
    return n, dp, prev_list, time_list, w


def ready(prev_list):
    for prev in prev_list:
        if dp[prev] == float('inf'):
            return False
    return True


ipt = sys.stdin.readline
t = int(ipt())
for _ in range(t):
    n, dp, prev_list, time_list, w = init()
    while True:
        finished = True
        for i in range(1, n+1):
            if dp[i] == float('inf') and ready(prev_list[i]):
                dp[i] = time_list[i] + max([dp[prev] for prev in prev_list[i]])
                finished = False
        if finished:
            break
    sys.stdout.write(f'{dp[w]}\n')