백준 1005번: ACM Craft (Python)

접근

위상정렬에 DP를 더한 문제였는데 둘다 기본적인 수준으로만 섞여있어서 간단한 문제였다.

위상 정렬 기본 문제: 2021.06.20 - [코딩/백준 (Python)] - 백준 2252번: 줄 세우기 (Python)

백준 2252번: 줄 세우기 (Python)

기본적인 위상 정렬 알고리즘에 DP를 새로 작성해주되, DP[i] 는 i 를 완성하기까지 필요한 시간을 갱신하면서 저장해주면 된다.

코드

import sys
from collections import deque

t = int(sys.stdin.readline())
for _ in range(t):
    n, k = map(int, sys.stdin.readline().split())
    cost = [0] + list(map(int, sys.stdin.readline().split()))
    tree = [[] for __ in range(n + 1)]
    in_degree = [0] * (n + 1)
    dp = [0] * (n + 1)
    for __ in range(k):
        a, b = map(int, sys.stdin.readline().split())
        in_degree[b] += 1
        tree[a].append(b)
    q = deque()
    for i in range(1, n + 1):
        if in_degree[i] == 0:
            q.append(i)
            dp[i] = cost[i]
    while q:
        now = q.popleft()
        for i in tree[now]:
            in_degree[i] -= 1
            dp[i] = max(dp[now] + cost[i], dp[i])
            if in_degree[i] == 0:
                q.append(i)
    ans = int(sys.stdin.readline())
    print(dp[ans])

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!