[C++] 백준 2056 : 작업

 

 

 

문제

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.

 

몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)

 

모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.

 

 

 

입력

 

첫째 줄에 N이 주어진다.

두 번째 줄부터 N+1번째 줄까지 N개의 줄이 주어진다. 2번째 줄은 1번 작업, 3번째 줄은 2번 작업, ..., N+1번째 줄은 N번 작업을 각각 나타낸다. 각 줄의 처음에는, 해당 작업에 걸리는 시간이 먼저 주어지고, 그 다음에 그 작업에 대해 선행 관계에 있는 작업들의 개수(0 ≤ 개수 ≤ 100)가 주어진다. 그리고 선행 관계에 있는 작업들의 번호가 주어진다.

 

 

 

출력

 

첫째 줄에 모든 작업을 완료하기 위한 최소 시간을 출력한다.

 

 

---

 

 

문제 해결

 

문제에서 K번 작업의 선행 작업들의 번호는 모두 1이상 K-1 이하라는 조건이 주어졌으므로 dynamic programming 기법을 사용할 수 있습니다. 해결 알고리즘은 간단합니다. K번 작업의 선행 작업들 중 가장 마지막까지 수행된 작업의 시간에 K번의 작업시간을 더해줍니다.

 

 

각 작업이 걸리는 시간을 저장하는 배열을 arr_time[],

dp[i]에 i번 작업이 완료되는 데 걸리는 최소 시간,

task[i][]에 i번 작업의 선행 작업

을 저장하겠습니다.

 

 

한 가지 주의사항이 있습니다. 문제를 잘 읽어보면 선행 작업이 없는 작업은 최소 한 개 이상이며 1번이 그러하다고 적혀있습니다. r을 i번의 선행 작업 번호라고 한다면, dp[i] = max(dp[i], dp[r] + arr_time[i]) 처럼 작성하면 선행 작업이 없는 작업일 때는 이 명령을 수행하지 않으므로 엉뚱한 결과가 나올 수 있습니다. 

 

 

다음과 같은 입력이 주어졌다고 가정하겠습니다.

5

5 0

3 1 1

3 1 2

3 1 3

100 0

 

위 상황은 5개의 작업 중 1번부터 4번까지는 (1 - 2 - 3 - 4)로 연쇄적이고, 5번은 독립적입니다.

 

 

dp[i] = max(dp[i], dp[r] + arr_time[i])로 수행한 결과는 잘못된 값인 14가 나옵니다. 이유는 마지막 입력인 5번 작업은 선행 작업이 없으므로 max 문장이 수행되지 않기 때문입니다. 옳은 결과인 100을 출력하려면 선행 작업이 없는 경우를 대비하여, 선행 작업의 시간이 0 또한 가능하게 만들어줍니다.

 

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

int n, m, ans, arr_time[10001], dp[10001];
vector<int> task[10001];

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> arr_time[i] >> m;

		while (m--) {
			int pretask;
			cin >> pretask;
			task[i].push_back(pretask);
		}
	}

	dp[1] = arr_time[1];

	for (int i = 2; i <= n; i++) {
		int max_pretask = 0;

		for (auto r : task[i])
			max_pretask = max(max_pretask, dp[r]);

		dp[i] = max_pretask + arr_time[i];

		ans = max(ans, dp[i]);
	}

	cout << ans;
}