작업
위상정렬 문제에 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값을 업데이트해 나가는 과정을 나타내 보았다.
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))
틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다!
감사합니다.👍
[꼭 다시 풀어보기]