[백준 1516] 게임 개발

위상정렬 + DP 문제이다.

 

자신의 전에 세워진 건물들 중 가장 시간이 많이 걸린 녀석 꺼 + 자기꺼 더해주면 된다.

 

건물을 동시에 올릴 수 있으므로 1 → 3 이고 2 → 3 일 경우에는

1, 2 중 더 오래 걸리는 놈의 시간 + 3을 짓는 시간으로 고려해줘야하기 때문이다.

 

---

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>

#define SIZE 501

using namespace std;

int N;
int inbound[SIZE] = { 0,};
int dp[SIZE] = { 0,};
int cost[SIZE];
vector<vector<int>> graph(SIZE);

void solve()
{
    queue<int> q;

    // 진입차수 0인거 먼저 넣어주기
    for (int i = 1; i <= N; i++)
    {
        if (inbound[i] == 0)
        {
            q.push(i);
            dp[i] = cost[i];
        }
    }

    int cur, next;

    while (!q.empty())
    {
        cur = q.front();
        q.pop();

        for (int i = 0; i < graph[cur].size(); i++)
        {
            next = graph[cur][i];
            inbound[next]--;
            dp[next] = max(dp[cur], dp[next]);

            if (inbound[next] == 0)
            {
                dp[next] += cost[next];
                q.push(next);
            }
        }
    }
}

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

    cin >> N;

    int x;
    for (int i = 1; i <= N; i++)
    {
        cin >> cost[i];
        while (1)
        {
            cin >> x;
            if (x == -1)
            {
                break;
            }
            graph[x].push_back(i);
            inbound[i]++;
        }
    }

    solve();

    for (int i = 1; i <= N; i++)
    {
        cout << dp[i] << "\n";
    }

    return 0;
}