[백준] 2056-작업(C++)

문제링크:www.acmicpc.net/problem/2056

2056번: 작업

 

 

dp문제라기보다는 그리디 문제에 가까웠습니다. 

 

문제에서 주는 조건들입니다.

 

• 항상 선행작업부터 처리한다.
• 선행작업의 번호는 자신의 번호보다 작다.
• 선행작업이 아니라면 동시작업이 가능하다.

3가지 규칙에 의해서 1번작업부터 오름차순으로 작업시간을 정의내리면 결과값을 도출할 수 있습니다.

 

 

굳이 점화식으로 나타내자면,   dp[n] = current_time + max( 1~dp[n-1]) 일것입니다. 

그리고 이러한 값들중 가장 큰 값이 결과값이 되는 것입니다. 

 

문제의 원리를 이해하셨다면 구현자체는 전혀 어려움이 없으셨을겁니다.

 

 

아래는 정답코드입니다. 

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

int dp[10001] = { 0, };
int n;
int time = 0, cnt = 0, value = 0;
int result = 0;

int main(void) {

	iostream::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> time >> cnt;
		if (cnt == 0) {
			dp[i] = time;
			continue;
		}
		int maxed = 0;
		for (int j = 0; j < cnt; j++) {
			cin >> value;
			maxed = max(maxed, dp[value]);
		}
		dp[i] = time + maxed;
	}
	/*
	for (int i = 1; i <= n; i++)
		cout << dp[i] << endl;
	*/


	for (int i = 1; i <= n; i++)
		result = max(result, dp[i]);

	cout << result << endl;


	return 0;
}