백준 2056번 - 작업

www.acmicpc.net/problem/2056

2056번: 작업

기초적인 DP 문제였다.

인접리스트를 사용하는게 해결 방법이였다.

 

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t, n, x;
    int time[10004];
    vector<int>must[10004];
    int dp[10004];
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> time[i] >> n;
        for (int j = 0; j < n; j++) {
            cin >> x;
            must[i].push_back(x);
        }
    }
    int ans = 0;
    for (int i = 0; i < t; i++) {
        int s = must[i].size();
        int max_num = 0;
        for (int k = 0; k < s; k++) {
            max_num = max(max_num, dp[must[i][k] - 1]);
        }
        dp[i] = max_num + time[i];
        ans = max(ans, dp[i]);
    }
    cout << ans << "\n";
}

골드 4 치고는 어렵지 않은 문제였다. 한 실버 1정도 난이도 인듯..