[백준 c++] 1516 게임 개발

문제

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

풀이

DFS + DP
6번째 건물을 짓기 위해서는 3 4 2 5 건물이 선행되어야하고 각 건물의 선행 건물을 아래방향으로 적었다. dfs로 깊이 탐색을 할 수 있는 그래프가 보인다😲

최대 500개의 건물을 매번 새롭게 dfs하면 시간초과가 발생한다.
그래서 dp를 이용해서 메모이제이션을 해야한다.

3번째 건물을 dfs했을 때, dp[1], dp[2], dp[3]의 값을 구할 수 있고,
이후에 4번째 건물을 짓기 위해 3번째 건물을 지으려할 때 이미 저장한 dp[3]을 가져다 써서 시간을 줄일 수 있다.

    for (int i = 0; i < map[idx].size(); i++)
    {
        int x = map[idx][i];
        dp[idx] = max(dp[idx], go(x) + val[idx]);
    }

x는 각 건물마다 선행되어야하는 건물이다.

dp[idx] = max(dp[idx], go(x) + val[idx])
건물은 동시에 지어질 수 있다.
따라서 빨리 지어진 건물의 소요시간이 아니라
가장 늦게 짓는데 오래걸리는 것을 구해주면 되기 때문에 max를 이용해서 구해줬다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, t, val[501], dp[501];
vector<int> map[501];

int go(int idx)
{
    if (!map[idx].size())
        return val[idx];

    if (dp[idx])
        return dp[idx];

    for (int i = 0; i < map[idx].size(); i++)
    {
        int x = map[idx][i];
        dp[idx] = max(dp[idx], go(x) + val[idx]);
    }

    return dp[idx];
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> val[i];
        while (1)
        {
            cin >> t;
            if (t == -1)
                break;
            map[i].push_back(t);
        }
    }

    for (int i = 1; i <= n; i++)
        cout << go(i) << "\n";
}