Baekjoon 1005번 ACM Craft

문제

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

걸린 시간

01 : 54 : 16

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

vector<int> build;

int dp(int here, vector<vector<int>>& adj, vector<int>& cache){
    // 기저 사례
    if(adj[here].size() == 0) return build[here];
    // 메모이제이션
    int& ret = cache[here];
    if(ret != -1) return ret;
    // 재귀 호출
    for(int i = 0; i < adj[here].size(); i++){
        int next = adj[here][i];
        int cand = dp(next, adj, cache);
        ret = max(ret, cand);
    }
    return ret += build[here];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n, k;
        cin >> n >> k;
        build.resize(n);
        vector<vector<int>> adj(n);
        for(auto& i : build) cin >> i;
        int x, y;
        for(int i = 0; i < k; i++){
            cin >> x >> y;
            adj[y-1].push_back(x-1);
        }
        int w;
        cin >> w;
        vector<int> cache(n, -1);
        cout << dp(w-1, adj, cache) << "\n";
    }
    return 0;
}

건설 순서 규칙이 주어지고, 건설을 시작하려면 이전 단계 건물들의 건설이 완료되어야 한다. 풀이 방법이 직관적으로 보이는 예제 하나를 손으로 그려보면 다음과 같다.

5 10
100000 99999 99997 99994 99990
4 5
3 5
3 4
2 5
2 4
2 3
1 5
1 4
1 3
1 2
4

건설해야 할 건물의 번호 w 를 기준으로 건설의 진행 순서를 나타내었을 때, 건설은 동시에 시작될 수 있으므로 각 단계마다 건물들의 최대 건설 완료 시간을 반환하면 된다.

건물 간의 순서는 주어진 입력대로 항상 일정하므로 중복이 존재할 수밖에 없다. 각 단계에서 현재 건물을 완성시키는데 필요한 최대 시간을 메모이제이션하면 제한 시간 안에 통과할 수 있다.