[BaekJoon] 백준 2056번 : 작업

2056번 : 작업

어느 작업을 마치는데 걸리는 시간은 선행 작업을 하는데 걸리는 시간의 최댓값과 본인의 시간을 더하면 된다.

DP 를 이용해 모든 작업에 대한 종료 시간을 구하고 그 중 최댓값을 출력하면 된다.

---

import sys


def solution():
    for i in range(1, N + 1):
        info = list(map(int, sys.stdin.readline().rsplit()))
        infos.append(info)
        work[i] = info[0]

    for idx, info in enumerate(infos):
        if info[1] >= 1:
            hard_work = 0
            pre_works = info[2:]
            for pre_work in pre_works:
                hard_work = max(hard_work, work[pre_work])
            work[idx + 1] += hard_work

    return max(work)


if __name__ == "__main__":
    N = int(input())
    work = [0] * (N + 1)
    infos = []

    print(solution())