1005번 : ACM Craft

Backjoon Online Judge 

"1005번 : ACM Craft" 문제입니다.

문제 링크 : https://www.acmicpc.net/problem/1005

문제에서 순서대로 건물을 지어야 하고 그 순서가 규칙없이 주어지므로 먼저 vector에 각 건물의 선행순서를 저장했습니다.

 이후 특정 건물을 짓기 위해 그 건물을 짓는데 걸리는 시간과 가장 오래 걸리는 선행 건물을 짓는 시간의 합을 구했습니다. (특정 건물의 선행 건물 중 시간 소요가 가장 오래 걸리는 건물이 완성되면 다른 건물들은 완성 상태이다.)

 선행 건물에도 또 다른 선행순서가 존재할 수 있기 때문에 이 부분을 재귀를 통해 구현하였습니다.

아래는 코드 설명입니다.

 -먼저 순서를 저장할 건물 갯수(최대 1000개)만큼의 vector와 시간과 값을 저장할 배열을 만들었습니다.

 - 이후 특정 건물의 소요 시간을 알기위해 그 건물의 소요 시간과 선행 건물의 소요 시간 중 가장 큰 소요시간을 가지는 값을 더했고 이 과정에서 max 함수와 재귀를 이용했습니다.

코드는 C++로 작성하였습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
 
#define MAX 1001
 
using namespace std;
 
int time[MAX];
int result[MAX];
vector<int> rule[MAX];
 
int dp(int W) {
    int &answer = result[W];
    if (answer) {
        return answer;
    }
    answer = time[W];
    while (!(rule[W].empty())) {
        int prev = rule[W].back();
        rule[W].pop_back();
        answer = max(answer, time[W] + dp(prev));
    }
    return answer;
}
 
int main() {
    int T, N, K, W, temp1, temp2;
    cin >> T;
    while (T--) {
        cin >> N >> K;
        memset(result, 0, sizeof(result)); 
        for (int i = 1; i <= N; i++) {
            cin >> time[i];
        }
        for (int i = 0; i < K; i++) {
            cin >> temp1 >> temp2;
            rule[temp2].push_back(temp1);
        }
        cin >> W;
        cout << dp(W) << endl;
        for (int i = 0; i < MAX; i++) {
            rule[i].clear();
        }
    }
    cin >> W;
    return 0;
}