[Python] 백준 2056번: 작업

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

2056번: 작업

1. 위상 정렬이다. 각 노드마다 최소비용을 구하는 dp 문제이다.

2. 이전 노드들 중에 가장 큰 비용을 현재 노드의 비용과 더해간다.

3. dp 중에 가장 큰 값이 ans다

n = int(input())
dp = [0 for _ in range(n+1)]
graph = [[] for _ in range(n+1)]
for i in range(1, n+1):
    cost, m, *lst = map(int, input().split())
    dp[i] = cost
    for x in lst:
        graph[i].append(x)

for i in range(1, n+1):
    tmp = 0
    for j in graph[i]:
        tmp = max(tmp, dp[j])
    dp[i] += tmp
print(max(dp))