[백준] 2056번 작업 (파이썬)

문제링크 : https://www.acmicpc.net/problem/2056

난이도: GOLD IV

문제해결 아이디어

• dp문제
• dp에는 해당 인덱스까지의 소요시간을 저장하고 선행 인덱스들의 dp 값중 가장 큰 값에 소요시간을 더하는 방식으로 진행한다.

소스코드

import sys

input = sys.stdin.readline

n = int(input())

# dp에는 인덱스까지의 소요시간을 저장해야함
# 그러면 선행 인덱스는 어떻게 처리?

dp = [0] * (n+1)

for i in range(1,n+1):
    k = list(map(int, input().split()))
    time = k[0]

    _max = 0
    # 선행인덱스 배열을 순회하면서 가장 큰값에 소요시간을 더한다.
    for j in k[2:]:
        _max = max(_max, dp[j])

    dp[i] = time + _max

print(max(dp))