[BOJ][Python]1005 풀이

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

1005번: ACM Craft

import sys; ssr = sys.stdin.readline
sys.setrecursionlimit(10000)

def f(node):
    if dp_delay[node] == -1:
        results = []
        for child in build[node]:
            child_delay = f(child)
            results.append(child_delay)
        dp_delay[node] = delays[node] + max(results)
    return dp_delay[node]

t = int(ssr())
for _ in range(t):
    n, k = map(int, ssr().split())
    delays = [0] + list(map(int, ssr().split()))
    dp_delay = delays[:] # deepcopy
    build = [[] for _ in range(n+1)]
    for _ in range(k):
        x, y = map(int, ssr().split())
        build[y].append(x)
        if dp_delay[y] != -1:
            dp_delay[y] = -1
    tar = int(ssr())
    ans = f(tar)
    print(ans)

 

간만에 돌아온 백준 풀이 입니다. 골드 3이긴 한데 간단한 재귀로 풀리기 때문에 크게 어려운 문제는 아니란 생각이 들구요. 아마도 언어에 따라 재귀로 풀 수 없기 때문에 특정 풀이가 강요되고, 해당 풀이가 난이도가 어려운 풀이가 아닌가 생각합니다. 그것도 따로 공부를 해서 차차 추가해보도록 하겠습니다.

 

추가// 딱히 새로운 풀이라고 할만한게 없네요. 그냥 다들 dp를 사용한 것 같습니다.