[백준/C++] ACM Craft (No. 1005)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 특정 건물을 짓기 위해서 다른 건물을 먼저 지어야 된다는 선행조건이 있는 문제다.

 

이때, 각 건물은 동시에 지을 수 있다.

 

그러므로 특정 건물을 짓기 위해 필요한 시간을 아래와 같이 표현할 수 있다.

Build(X) = max( Build (X건물을 짓기 위해 사전에 지어야 하는 건물) ) + (X 건물만 짓는데 걸리는 시간)

그러므로 이 문제는 DP 문제로 생각할 수 있다.

 

X건물을 짓기 위한 다른 건물을 짓는 시간을 알면, X건물을 짓는데 걸리는 시간을 알 수 있기 때문이다.

(즉, 작은 문제를 해결함으로써 큰 문제를 해결할 수 있기 때문)

 

여기서 시간을 줄이기 위해서는 특정 건물을 짓는데 걸리는 시간을 배열에 저장했다.

(A건물을 짓는데 걸리는 시간을 이미 계산했다면, 중복 계산하지 않기 위해서)

 

[구현 참고]

- y건물을 짓기 위해 필요한 건물 x를 2차원 vector를 이용해 저장한다.

- 특정 건물만 짓는데 걸리는 시간을 1차원 vector에 저장한다.

- 하위 건물을 짓는 시간을 포함해 최종적으로 걸리는 시간을 1차원 vector에 저장한다.

 

 

 

​

[아이디어 정리]

1. 특정 건물을 짓기 위해 걸리는 총 시간은 [사전에 지어야하는 건물 중 가장 늦게 지어지는 건물의 시간 + 특정 건물만 짓는데 걸리는 시간]으로 표현할 수 있다. 
2. 특정 건물을 짓는데 걸리는 총 시간을 중복 계산하지 않도록 vector를 이용해 저장한다. (memoization)
3. 최종적으로 걸린 시간을 출력한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;


int DFS(int node, vector<vector<int>>& graph, vector<int>& TD, vector<int> &MEMO) //시간 return
{
    int &retT = MEMO[node];
    if (retT != -1) {
        return retT;
    }
    retT = 0;
    for (int i = 0; i < graph[node].size(); i++) {
        retT=max(retT,DFS(graph[node][i], graph, TD, MEMO));
    }
    retT += TD[node];
    return  retT;

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int tc;
    cin >> tc;
    for (int t = 0; t < tc; t++) {
        int N, K;
        cin >> N >> K;
        vector<int> TD(N + 1);
        vector<int> MEMO(N + 1,-1);
        for (int i = 1; i <= N; i++) {
            cin >> TD[i];
        }
        int x, y;
        vector<vector<int>>graph(N + 1);
        for (int i = 0; i < K; i++) {
            cin >> x >> y; //x이후 y
            graph[y].push_back(x);
        }
        int root;
        cin >> root;
        cout << DFS(root, graph, TD,MEMO) << "\n";
    }
    return 0;
}

 

---

최근에 DP에 문제를 많이 봐서 그런가 빠르게 구현하고 풀었다.

골랜디 돌렸는데 이런 우연이;;

하루일정을 골랜디 (1), 단계별로 문제풀기 (1), 알고스팟 진도로 바꿀까...

 

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