[백준 2056번] 작업 (python)

문제

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.

몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)

모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.

 

기록

(dp 15일차) 파이썬 packing 사용해보려고 한 번 더 제출했다. (packing : *변수 형태로 가변인자 받는 것. 여러 개의 인자가 tuple로 묶여 저장된다.) 문제는 일차원 배열을 사용해서 풀어서 그런가 간단했다.

 

dp[i]에는 i번째 작업이 끝나는 시간을 저장했다. 선행작업이 없다면 0시간 부터 시작할 수 있기 때문에 작업시간을 그대로 저장하고, 선행작업이 있다면 가장 늦게 끝나는 선행작업에 작업시간을 더하여 저장한다. 저장한 값들 중 가장 늦게끝나는 시간을 출력하면 성공:)

 

코드

import sys
input = sys.stdin.readline

n = int(input())
dp = [0]*(n+1)
for i in range(1, n+1):
    work, count, *pre = map(int, input().split())
    dp[i] = work
    for j in pre:
        dp[i] = max(dp[i], dp[j]+work)
print(max(dp))

1. 각 작업이 끝나는 시간을 저장할 일차원 dp 배열 생성

2. 선행작업이 없다면 그대로 작업시간을, 아니면 선행작업마다 max(dp[i], dp[j]+work)를 계산하여 가장 늦게 끝나는 선행작업에 작업시간을 더한값을 저장한다.

3. 가장 늦게 끝나는 작업의 완료시간을 출력한다.