BOJ 1516 : 게임 개발

• 문제 링크 : boj.kr/1516
• 난이도 : G3
• 태그 : DP

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n;
    cin >> n;
    vector<pair<int, vector<int>>> arr(n);
    for(auto &e : arr) {
        cin >> e.first;
        while(true) {
            int input;
            cin >> input;
            if(input == -1) break;
            e.second.emplace_back(input-1);
        }
    }

    vector<int> dp(n, 0);

    function<int(int)> func = [&](int k) -> int{
        if(dp[k]) return dp[k];
        dp[k] = 0;
        for(auto e : arr[k].second) {
            dp[k] = max(dp[k], func(e));
        }
        dp[k] += arr[k].first;
        return dp[k];
    };

    for(int i = 0; i < n; i++) {
        cout << func(i) << "\n";
    }

    return 0;
}

---

풀이

k를 짓기 이전에 지어야 하는 건물들의 배열을 $P_k$, k를 짓는 데에 걸리는 시간을 $T_k$라고 하자.

$dp[k] = max(dp[P_k [0]], dp[P_k [1]] , \cdots ,  dp[P_k [j]] ) + T_k $이다.

모든 건물을 짓는 것이 가능하다고 했으므로 재귀 DP를 이용하면 답을 구할 수 있다.