백준 2056 작업 C++

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

dp느낌으로 해결이 가능하다. . 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다

이 문장때문에 아래 풀이로 가능한 것이다.

d[i] = i의 사전작업까지 모두 포함해서 작업 i를 끝내는 데에 걸리는 시간

 
#include<iostream>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
 
int n, m, t[10001], d[10001];
vector<int> v[10001];
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int tm, num;
        cin >> tm >> num;
        t[i] = tm;
        while (num--) {
            int pre;
            cin >> pre;
            v[i].push_back(pre);
        }
    }
    //d[i] = i의 사전작업까지 다 포함해서 작업 i 끝내는데 드는 시간
    d[1] = t[1];
    for (int i = 2; i <= n; i++) {
        if (v[i].size() == 0) d[i] = t[i]; //사전 작업 없으면 그 작업 끝내는 시간
        else {
            int Max = -1;
            for (int j = 0; j < v[i].size(); j++) {
                if (Max < d[v[i][j]]) Max = d[v[i][j]];
            }
            d[i] = Max + t[i];
        }
    }
    //어떤 작업이 제일 마지막에 끝날지는 알 수 없지만, 필요 시간이 가장 긴게 마지막에 끝나는 것
    int ret = -1;
    for (int i = 1; i <= n; i++)
        if (ret < d[i]) ret = d[i];
    cout << ret;
    return 0;
}