[백준 / BOJ] 2056 작업

문제

출처 : www.acmicpc.net/problem/2056

2056번: 작업

N개의 수행할 작업과, 각 작업을 수행하는데 걸리는 시간이 주어진다.

작업에는 선행관계가 있고, 각 작업을 수행하기위해선, 해당 작업의 선행작업을 수행해야한다.

이때, 모든 작업을 수행하는데 걸리는 최소시간을 구하는 문제다.

 

풀이

재귀와 메모이제이션으로 풀리는문제다.

 

현재 작업 A를 수행해야하고 A의 선행 작업이 B,C,D라고 할때,

B,C,D가 걸리는 수행시간중 최댓값을 가져와서 A가 걸리는 시간을 더하면 A의 수행시간이 된다.

 

A의 수행시간 = max(B,C,D)의 수행시간 + A의 수행시간

모든 (선행 작업을 완료한) 작업은 동시에 수행할수있다. 따라서 B,C,D중 가장 오래걸리는 작업이 B,C,D가 모두 수행되는데 걸리는 시간이다.

이때, B,C,D들도 선행작업이 있을수있어서 바텀업 방식으로 구현했다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/2056%20%EC%9E%91%EC%97%85/main.cpp

devxb/JJUNalgo