[백준 2056] 작업

문제 링크 => 2056번: 작업 (acmicpc.net)

2056번: 작업

 

위상정렬 + 다이나믹 프로그래밍 문제이다.

 

먼저 작업들 간의 inDegree를 설정해야 한다.

 

즉, inDegree[x] = 0 인 경우에 다음 작업으로의 진행이 가능하고 그 다음 작업을 완료하기 위한

최소 시간을 정해야 한다.

 

 

위 그림과 같이 x1, x2, ..., xi를 현재 처리한 작업들이고 next를 그 다음 작업이라고 하자.

 

현재까지 작업을 완료하기 위한 최소 시간을 R(x) 라고 해보자.

 

R(next) 를 구하기 위해서는 R(x1), R(x2), ... , R(xi) 에 대한 정보와 next 작업의 걸리는 시간

즉, T[next] 가 필요하다.

 

next 작업까지 완료하기 위한 최소 시간을 구하기 위해서는 x1, x2, ..., xi 에 대한 작업들이 모두 처리가

된 시간들 중 최대 시간이 걸린 것을 기준으로 next 작업이 걸리는 시간을 더해줘야 한다.

 

왜냐하면 x1, x2, ..., xi 에 대한 작업들이 모두 작업을 완수하기 위해서는 x1, x2, ..., xi가 걸린 시간들

중에 최대 시간이 되어야만 하기 때문이다.

 

즉, 위 정보를 이용하여 Optimal Substructure 를 만들면 다음과 같다.

 

R(next) = max(R(x1), R(x2), ..., R(xi)) + T[next]

 

 

Solution Code

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define endl '\n'

using namespace std;

vector<int> v[10001];
int T[10001], inDegree[10001], Result[10001];

int solution(int n) 
{
	int result;
	queue<int> Q;
	for (int i = 1; i <= n; i++) {
		if (inDegree[i] == 0) {
			Q.push(i);
			Result[i] = T[i];
		}
	}

	result = 0;
	while (!Q.empty()) {
		int x = Q.front();
		Q.pop();
		if (!v[x].size()) result = max(result, Result[x]);

		for (int next : v[x]) {
			Result[next] = max(Result[next], Result[x] + T[next]);
			if (--inDegree[next] == 0) {
				Q.push(next);
			}
		}
	}

	return result;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int m, x;
		cin >> T[i] >> m;
		for (int j = 0; j < m; j++) {
			cin >> x;
			v[x].push_back(i);
			inDegree[i]++;
		}
	}

	cout << solution(n);

	return 0;
}