python 백준 2056 작업

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

문제 해석

• 작업에는 선행되어야 할 작업이 있다

• 작업들은 정렬이 잘 되어 있어 K번 작업에 필요한 선행작업은 K-1번째 작업 이하로만 구성되어 있다

• 그렇기에 graph를 그려 선행 작업들을 기록해둘 필요가 없다

• 1번부터 N번까지 작업들을 순회

• 해당 작업에 필요한 시간 + 선행 작업이 완료되는데 걸리는 시간을 구한다

import sys
input = sys.stdin.readline

N = int(input())
check = [0]*(N+1)
for node in range(1,N+1):
    time,P,*works = map(int,input().split())
    if P:
        added_time = 0
        for work in works:
            added_time = max(added_time,check[work])
        time += added_time
    check[node] = time
print(max(check))