백준 1005번 - ACM Craft

www.acmicpc.net/problem/1005

1005번: ACM Craft

옛날부터 이문제 한번 풀어보고 싶었는데 골드 3에 dp라 뭔가 엄청 어려울 것 같아서 못풀었었다.

오늘 날잡고 어떻게든 한번 풀어보자 하고 풀어봤다.

 

처음 문제를 봤을때 재귀가 떠올랐다. 이런 문제의 경우 dfs라고 하는게 맞겠지만..

분명 dp와 재귀를 통해 풀 수 있을것 같은데 이게 맞을까 싶어서, 해결법이 맞는지를 한참 고민했다.

 

아무리 봐도 다른 방법은 떠오르지 않아서 그냥 풀었는데 다행히 맞았다.

 

해결법은 다음과 같다.

 

1. 구하고자 하는 노드(문제에서는 건물)의 실행시간을 구하기 위해서 선행 노드들을 모두 방문한다.

2. 1번 과정을 재귀적으로 반복해서 각 노드들의 선행 노드들의 실행시간을 구한 뒤 답을 찾는다.

 

이때 중요한점은 조건을 설정할 때 내가 구하고 싶은 노드만 구한다. 

다시 말해 문제에서 거리를 알 필요가 없는 노드는 방문조차 안한다는 말이다.

 

코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int dist[1004];
vector<int>arr[1004];
int dp[1004];
bool check[1004];
 
int find(int x) {
    if (arr[x].size() == 0) return dist[x - 1];
    int max_num = 0;
    for (int i = 0; i < arr[x].size(); i++) {
        int node = arr[x][i];
        if (check[node] == false) {
            dp[node] = find(node);
            check[node] = true;
        }
        max_num = max(max_num, dp[node]);
    }
    return max_num + dist[x - 1];
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t, n, k, a, b, x;;
    cin >> t;
    while (t--) {
        memset(dist, 0, sizeof(dist));
        memset(arr, 0, sizeof(arr));
        memset(dp, 0, sizeof(dp));
        memset(check, false, sizeof(check));
        cin >> n >> k;
        for (int i = 0; i < n; i++) cin >> dist[i];
        for (int i = 0; i < k; i++) {
            cin >> a >> b;
            arr[b].push_back(a);
        }
        cin >> x;
        cout << find(x)<< "\n";
    }
}

재귀함수만 잘 짜준다면 코드 자체는 복잡하지 않다.