[백준] 2056 작업

문제

• 작업 N개와 각 작업마다 걸리는 시간이 정수로 주어진다.
• K번 작업은 K-1번 이하의 작업 중 선행 관계의 작업을 가질 수도 있다.
• 그 때 모든 작업을 완료하기 위한 최소 시간 구하기

 

• 3 <= N <= 10,000
  1 <= 시간 <= 100 

 

풀이

• dp[K] : K번 작업을 완료하기 위한 최소 시간
  • dp[1] : 첫 작업 완료 시간
  • dp[k] = 1 ~ k-1 번까지 작업까지 중 선행 관계의 작업 중 가장 오래 걸리는 시간 + k 번째 작업의 시간 

 

N = int(input())
prior = [0] + [list(map(int, input().split())) for _ in range(N)]

# dp[K] : K번 작업을 완료하기 위한 최소 시간
dp = [0] * (N+1)
dp[1] = prior[1][0]    # 첫 작업 완료 시간

for i in range(2, N+1) :
    # 선행 관계의 작업 중 가장 오래 걸리는 시간 + i번째 작업
    for k in prior[i][2:] :
        dp[i] = max(dp[i], dp[k])
    dp[i] += prior[i][0]

print(max(dp))

 

References

• 백준 DP