BOJ 1005 [ACM Craft]

BOJ ACM Craft : www.acmicpc.net/problem/1005

1005번: ACM Craft

우선 주어진대로 그림을 그려보니, 그래프가 나왔다.

 

어떻게 이어볼까,, 고민하다가 역으로 이어보니 답이 나왔다.

 

페이지에 있는 테스트케이스를 토대로 그려본다.

 

입력 :

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

대략 이런그림이 나온다.

 

내가 필요한 것은 4에 도달하기까지의 시간이다.

 

먼저 목표인 4부터, 무엇을 개발해야 하는지 따져본다.

 

1, 2, 3을 다 개발하면 4를 개발할 수 있는데, 그러면 그때까지의 최대시간은 얼마인가?를 생각해보면

 

점화식을 구할 수 있다.

 

dp[4] = max(dp[1], dp[2], dp[3]) + arr[4]

식을 도출한 뒤, 재귀를 이용해 dp[1], dp[2], dp[3]도 똑같은 방식으로 구할 수 있다.

 

값이 나온 목적지는 배열에 저장해 두고, 나중에 다시 호출되면 써먹는다.

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int values[1001];
 
int N, K;
 
int mem[1001];
 
vector<int> v[1001];
 
int recur(int dest)
{
    if (mem[dest] != -1)
    {
        return mem[dest];
    }
 
    int result = 0;
    
    for (int i = 0; i < v[dest].size(); i++)
    {
        result = max(result, recur(v[dest][i]) + values[dest]);
    }
 
    if (v[dest].size() == 0)
    {
        result = values[dest];
    }
 
    mem[dest] = result;
    return result;
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    int t;
    cin >> t;
    for (int test_case = 0; test_case < t; test_case++)
    {
        cin >> N >> K;
        
        fill_n(mem, N+1, -1);
        for (int i = 0; i <= N; i++)
        {
            v[i].clear();
        }
 
        for (int i = 1; i <= N; i++)
        {
            cin >> values[i];
        }
 
        for (int i = 0; i < K; i++)
        {
            int pre, post;
            cin >> pre >> post;
 
            v[post].push_back(pre);
        }
 
        int dest;
        cin >> dest;
 
        cout << recur(dest) << endl;
    }
    return 0;
}