[백준] 2056 파이썬

문제

---

• 백준 2056 (골드 4)

백준 2056

n가지 작업이 주어지는데, 각각의 작업에 걸리는 시간과 선행되어야 하는 작업이 주어진다.
여기서 모든 작업을 완료하기 위해 필요한 최소 시간을 구하는 문제이다.
이때 선행 관계가 없는 작업들은 동시에 수행 가능하다는 것이 문제의 조건이다.

내 코드

---

선행 작업에 걸리는 시간이 뒤 작업들의 시간에 영향을 미치므로 dp를 통해서 구현해보았다.
우선 각 작업이 완료되기 위한 최소 시간을 담을 dp 테이블을 하나 생성한다.
여기서 dp 테이블을 계속 탐색하면서 각 작업의 선행 작업들이 모두 완료되었다면 그 중 가장 오래 걸린 시간에 해당 작업의 수행 시간을 더해서 dp 테이블을 채워나간다.
dp 테이블이 모두 채워지면 그 중 가장 긴 시간을 출력하면 모든 작업을 완료하기 위해 필요한 최소 시간이 된다.

import sys
input = sys.stdin.readline

n = int(input())
works = [list(map(int, input().split())) for _ in range(n)]
dp = [0] * n

dp[0] = works[0][0]

while 0 in dp:
    for i in range(n):
        if dp[i] == 0:
            max_time = 0
            temp = False
            for j in range(works[i][1]):
                if dp[works[i][2 + j]-1] == 0:
                    temp = True
                    break
                else:
                    max_time = max(max_time, dp[works[i][2 + j]-1])
            if not temp:
                dp[i] = max_time + works[i][0]

print(max(dp))

다른 사람들의 코드를 확인해보니 선행 관계의 작업들이 항상 번호가 작다는 것을 활용하여 코드가 훨씬 간결하게 나온 것을 확인할 수 있었다.
문제의 조건을 잘 파악하면서 코드를 작성해 나가야겠다.