다이나믹 프로그래밍과 위상정렬을 이용하여 푸는 문제
먼저, 위상정렬을 이용하여 작업간의 순서를 빠른 순서대로 큐에 저장해둔다.
Queue<Integer> order = new LinkedList<>();
그리고 dp 일차원 배열에는 작업의 최소 완료시간을 저장한다.
dp[n] : 작업 n을 완료하기 위해 필요한 최소 시간
큐에서 가장 먼저 실행되는 작업(n)부터 하나씩 꺼낸다.
dp[n] = dp[n] + time[n] 으로, dp[n]에 해당 작업의 소요시간(time[n])을 더해준다.
(제일 처음 큐에서 꺼내지는 작업은 0 + time[n] 이 될 것이다.)
해당 작업(n) 다음에 수행되어야할 작업(m)의 시작 시간을 갱신시켜준다.
dp[m] = Math.max(dp[m], dp[n])
Math.max()로 최대값을 구해서 dp[m]에 넣어주는 이유는
어떤 작업(m)이 있을 때, 그 작업 직전에 수행되는 여러 작업들 중 가장 늦게 끝나는 시간이 이 작업(m)의 시작시간이 되기 때문이다.
그리고 다음번에 큐에서 작업 m이 꺼내지게 되면
(m이 n보다 늦게 작업이 시작되므로 위상정렬을 하게 되면 n보다 늦게 큐에서 꺼내짐)
기존의 dp[m]에 소요시간(time[m])만 더해주면 되는 것이다.
아래 그림은 백준 2056번 문제 예제를 나타낸 것이다.
소스코드 :
'BOJ' 카테고리의 다른 글
[백준 6236번] 용돈 관리 (java) (0) | 2021.03.01 |
---|---|
[백준 5052번] 전화번호 목록 (java) (0) | 2021.02.27 |
[백준 2670번] 연속부분최대곱 (java) (0) | 2021.02.25 |
[백준 2240번] 자두나무 (java) (0) | 2021.02.25 |
[백준 1655번] 가운데를 말해요 (java) (0) | 2021.02.24 |