파이썬 백준 2056번 : 작업

문제 

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

 

 

풀이

알고리즘

다이나믹프로그래밍

 

입력값이 리스트로 저장된 work, 완료된 시간을 저장할 done_time을 리스트로 선언한다.

해당 작업의 수행시간은 '선행작업시간의 종료시간(있다면) + 해당 작업의 수행시간' 이다.

이때 선행작업이 여러개라면 그 중 가장 긴 시간이 wait_time에 해당한다.

 

입력 예시 1번의 경우 최종적으로 완성된 done_time은 다음과 같다. 

done_time = [5, 6, 9, 11, 12, 19, 23]

이중 가장 큰 값을 출력한다. 

 

import sys
N=int(sys.stdin.readline())
work=[]
for _ in range(N):
    work.append(list(map(int,sys.stdin.readline().split())))
done_time=[0]*(N) #시간을 저장할 배열

for j in range(N):
    i=2
    wait_time=0
    for _ in range(work[j][1]): # 선행 작업의 개수만큼 반복
        prev=work[j][i] #prev는 선행작업을 의미
        if wait_time<done_time[prev-1]: #만약 선행작업의 끝나는 시간에 따라 wait_time 업데이트
            wait_time=done_time[prev-1]
        i+=1 #다음 선행 작업

    done_time[j]=wait_time+work[j][0] # 기다린 시간 + 수행시간 으로 해당 작업의 done_time 업데이트
print(max(done_time)) #가장 오래 걸린 시간 출력