[백준 2056번] 작업 (java)

2056번: 작업

 

다이나믹 프로그래밍과 위상정렬을 이용하여 푸는 문제

먼저, 위상정렬을 이용하여 작업간의 순서를 빠른 순서대로 큐에 저장해둔다.

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번 문제 예제를 나타낸 것이다.

 

 

소스코드 :