[백준] 1005 ACM Craft

문제

• 매 게임 시작 시 N개의 건물을 짓는 순서가 K개 주어질 때, 특정 건물을 가장 빨리 지을 수 있는 최소 시간 찾기
  • 모든 건물은 각각 건설을 시작해 완성될 때 까지 Delay가 존재한다.
  • 2 <= N <= 1000
  • 1 <= K <= 100,000

 

풀이

• 처음엔 위상 정렬 문제라고 생각했는데, W까지만 지으면 되고 그 외 경로는 무시해야 한다.
• DP 로 해결할 수 있다.
  • dp[n] : n번째 건물 지을 때까지의 최소 시간
  • n 건물을 짓는데 a, b 건물이 선행되어야 할 때, a 건물과 b 건물 짓는데 최소 시간이 곧 n 건물 짓는데 최소시간과 같다. 
  • 따라서, n 건물을 짓기 위해 선행 되어야할 건물들의 최소 시간들을 비교하면서 top-down 방식으로 구현할 수 있다.
• sys.stdin.readline 사용 안하면 시간 초과 난다.

 

from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def calc_time(now):
    if now not in graph :   # 선행 건물이 없는 경우
        return delay[now]
    if dp[now] != -1 :      # 이미 최소시간을 구한 경우 (Memoization)
        return dp[now]
    
    # 각 선행 건물의 최소 시간 비교
    for pre in graph[now]:
        dp[now] = max(dp[now], calc_time(pre))
    dp[now] += delay[now]   # 현재 건물 짓는데 드는 시간 더하기
    return dp[now]

for _ in range(int(input())):
    N, K = map(int, input().split())
    delay = [0] + list(map(int, input().split()))   # 건물 짓는데 드는 시간
    graph = defaultdict(list)                       # 각 건물별 선행 리스트
    for _ in range(K):
        a, b = map(int, input().split())
        graph[b].append(a)    # a -> b
    W = int(input())

    # dp[n] : n 건물 짓는데 드는 최소 시간
    dp = [-1] * (N+1)
    print(calc_time(W))

 

References

• 백준 1005번
• 2023.04.28 오늘의 문제