ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • BOJ 1005 [ACM Craft]
    알고리즘 풀이/DP(동적계획법) 2021. 3. 10. 22:19

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

     

    1005번: ACM Craft

    첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부

    www.acmicpc.net

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

     

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

     

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

     

    입력 :

    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]도 똑같은 방식으로 구할 수 있다.

     

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    #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;
    }
    cs
    반응형

    '알고리즘 풀이 > DP(동적계획법)' 카테고리의 다른 글

    BOJ 11726 [2xn 타일링]  (0) 2018.09.25
    BOJ 1463 [1로 만들기]  (0) 2018.09.25

    댓글

Designed by Tistory.