[백준] 작업 2056번 C++ 풀이

https://www.acmicpc.net/problem/2056

2056번: 작업

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v[10001];
int dp[10001];
int Time[10001];
int N;
int main(void)
{
	cin >> N;
	int cost, num;
	for (int i = 0; i < N; i++)
	{
		cin >> cost >> num;
		Time[i] = cost;
		for (int j = 0; j < num; j++)
		{
			int temp;
			cin >> temp;
			v[i].push_back(temp-1); // 총 N개가 있다면 0~N-1번으로 모든 번호를 정할겁니다.
		}
	}

	int res = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < v[i].size(); j++)
		{
			dp[i] = max(dp[i],dp[v[i][j]]); 
            // i번째의 선행작업들중 가장 오래 걸리는 시간을 dp[i]에 저장
		}
		dp[i] += Time[i]; // i번째의 작업시간을 마지막에 더해줍니다.
		res = max(res,dp[i]); // 최대시간이 답이라 max 사용
	}

	cout << res;
}

dp[i]는 i번째 작업을 완료하기 위해 걸리는 최대시간을 저장해줍니다.

dp[i]는 i번째의 선행작업들이 걸리는 최대시간에 i번째의 작업시간을 더해주면 i번째 작업을 완료하는데 걸리는 시간이 됩니다.