작업

위상정렬 문제에 DP가 추가된 응용 문제이다. 방향을 못잡아서 이틀정도 헤맸는데, 하단의 알고리즘 분류를 참고해서 DP문제 라는 것을 확인한 후에 겨우 풀 수 있었다.

다른 위상정렬 문제와 동일하지만, 여기에 DP를 활용해 해당 작업을 마치는데 걸리는 시간을 저장한다. 이렇게 각각의 작업에 대해 걸리는 시간들을 체크하고, 가장 큰 값을 출력하면 된다.

  • bridge - 간선 정보 저장
  • time - 해당 작업을 수행하는데 걸리는 시간 저장
  • left - 선행작업이 현재 몇개 남았는지 저장
  • dp - 시작 시간부터 해당 작업을 끝마치는데 까지 걸리는 시간 저장
7
5 0
1 1 1
3 1 2
6 1 1
1 2 2 4
8 2 2 4
4 3 3 5 6

위의 입력에 대해 그래프와 DP값을 업데이트해 나가는 과정을 나타내 보았다.

Crepe

CODE

from collections import deque
import sys
read = sys.stdin.readline

n = int(read())
#간선 정보 저장
bridge = dict()
#작업에 걸리는 시간 저장
time = list(0 for _ in range(n+1))
#선행작업이 몇개 남았는지 저장
left = list(0 for _ in range(n+1))

for i in range(1, 1+n):
    tmp = list(map(int, read().split()))
    if tmp[1] != 0:
        for j in range(2, tmp[1]+2):
            if tmp[j] not in bridge:
                bridge[tmp[j]] = []
            bridge[tmp[j]].append(i)
    left[i] = tmp[1]
    time[i] = tmp[0]
#시작 시간부터, 해당 작업까지 걸리는 시간을 저장
dp = list(0 for _ in range(n+1))

point = deque([])
for i in range(1, n+1):
    if left[i] == 0:
        point.append(i)
        #바로 시작할 수 있는 작업인 경우,
        #DP를 해당 작업을 수행하는데 걸리는 시간으로 저장해놓는다.
        dp[i] = time[i]

while point:
    a = point.popleft()
    if a in bridge:
        for i in bridge[a]:
            left[i] -= 1
            dp[i] = max(dp[i], dp[a]+time[i])
            if left[i] == 0:
                point.append(i)
print(max(dp))


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]