[알고리즘][Python] 백준(BOJ) 2056 작업_파이썬

 

2056 작업    www.acmicpc.net/problem/2056

2056번: 작업

 

 

 

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍, 그래프 이론, 위상 정렬

 

 

 

 

 

 

 

풀이

<내용>

• K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이므로 dp로 해결할 수 있다.
• 해당 작업에 걸리는 시간을 times에 저장하고 선행 작업을 graph에 저장한다.
• for문을 돌면서 해당 작업에 필요한 선행 작업들의 max 시간을 더한다.
• 작업에 필요한 시간들 중 최댓값을 출력한다.

 

 

<코드>

import sys
input = sys.stdin.readline

n = int(input())
times = [0] * (n+1)
graph = {}
for i in range(1, n+1):
    lst = list(map(int, input().split()))
    times[i] = lst[0]
    if lst[1] == 0:
        continue
    for j in lst[2:]:
        if i in graph:
            graph[i].append(j)
        else:
            graph[i] = [j]
            
for i in range(1, n+1):
    if i in graph:
        time = 0
        for j in graph[i]:
            time = max(time, times[j])
        times[i] += time
        
print(max(times))