문제 링크

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

문제 설명

• 1~N 번 작업마다 걸리는 시간, 선행해야 하는 작업이 주어진다

• 선행해야 하는 작업이 없는 작업들끼리는 동시에 작업이 가능하다

• 모든 작업을 끝내는데 걸리는 시간 출력

풀이

• 1번 작업부터 돌면서

• 현재 작업까지 총 소요 시간 = 현재 작업의 소요 시간 + max(선행 작업의 총 소요 시간)

DP로 푼 이유

• 처음에는 위상 정렬인가 했는데 동시 작업이 가능하기 때문에 아니었다

• 브루트 포스나 그리디로는 어려워 보였다

• 선행해야 하는 작업들이 언제 끝나는지는 그 이전에 언제 끝나는지에 결정된다

• 선행 작업 중 가장 마지막에 끝나는 작업이 끝나야 시작이 가능하다

• 선행 작업이 없는 작업은 그 시간만큼 걸린다

시행 착오

• 선행 작업에 개수에 따라 정렬해야 하나 했는데

  • 이건 오답이 나온다

• 순회 중 현재 작업은 선행 작업보다 무조건 크기 때문에 다른 정렬이 따로 필요없다

• 선행 작업 중 모든 작업이 끝나야 되기 때문에 시간이 가장 큰 값을 골라야 하는데 작은 값을 골랐다

코드

def init():
    import sys
    ipt = sys.stdin.readline
    n = int(ipt())
    adj_list = [[0,[]] for i in range(n+1)]
    dp = [0] * (n+1)
    for i in range(1, n+1):
        temp_list = list(map(int, ipt().split()))
        adj_list[i][0] = temp_list[0]
        adj_list[i][1] = temp_list[2:]
        if not temp_list[1]:
            dp[i] = temp_list[0]
    return n, adj_list, dp


n, adj_list, dp = init()
for i in range(1, n+1):
    time, prev_list = adj_list[i]
    if not prev_list:
        continue
    max_time = float('-inf')
    for prev in prev_list:
        max_time = max(max_time, dp[prev])
    dp[i] = time + max_time
print(max(dp))