Today's special moments become memories of tomorrow.

BOJ

[백준 2056번] 작업 (java)

lotus lee 2021. 2. 26. 18:12

 

2056번: 작업

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해

www.acmicpc.net

 

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

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

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

 

 

소스코드 :