[1005]ACM craft

처음에는 다익스트라 알고리즘의 변형으로 문제를 풀려고 하였다. 알고리즘을 짜는데 상당히 오랜 시간이 걸렸지만(stl 등의 c++ 사용법을 익히는 등의 이유로) 정답은 얼추 잘 맞추는거 같았다. 하지만 메모리 초과 문제가 발생하였다.

 

초안:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {

    short times = 0;
    cin >> times;


    for (int t = 0; t < times; t++)
    {
        vector<short> relations[1001];
        int result_cost[1001];
        int costs[1001];
        priority_queue<pair<short, int>, vector<pair<short, int>>, less<pair<short, int>>> pq;
        int nob = 0, nor = 0;
        cin >> nob >> nor;

        for (int i = 1; i <= nob; i++)
        {
            cin >> costs[i];
            result_cost[i] = costs[i];
        }
        for (int i = 0; i < nor; i++)
        {
            int n = 0, m = 0;
            cin >> n >> m;
            relations[n].push_back(m);
        }

        short end_point = 0;
        cin >> end_point;
        pair<int, short> p = make_pair(costs[1], 1);
        pq.push(p);
        while (!pq.empty())
        {
            pair<int, short> current_point = pq.top();
            pq.pop();
            for (auto& ele : relations[current_point.second])
            {
                if (result_cost[current_point.second] + costs[ele] > result_cost[ele])
                {
                    result_cost[ele] = result_cost[current_point.second] + costs[ele];
                }
                pq.push(make_pair(result_cost[ele], ele));
            }
        }
        if (costs[end_point] > result_cost[end_point])
            result_cost[end_point] = costs[end_point];
        cout << result_cost[end_point];
    }
}

 

 

이번엔 동적 프로그래밍을 활용하여 풀기로 하였다. 처음부터 코드를 스스로 짠 건 아니고 다른 사람이 풀은 걸 보고 떠올려서 작성해보았다. 이 코드가 보여주는 동적 프로그래밍의 특징은 테이블을 만들어서 거기에 기록한다는 점이다. 테이블에 기록된 작은 문제의 값을 이용하여 보다 큰 sub problem도 해결해나갈수 있다는 점도 그렇다.

 

#include <bits/stdc++.h>

using namespace std;

int times = 0;

int b,k,n,m,e,dp[1001];
int arr[1001];
bool path[1001][1001];

int func(const int& a){
    if(dp[a] != -1) return dp[a];
    int mt = 0;
    for(int i = 1; i <= b; i++)
    {
        if(path[i][a] != true) continue;
        mt = max(mt, func(i));
    }
    dp[a] = mt + arr[a];
    return dp[a];
}

int main(){
    cin >> times;
while(times--)
    {
        memset(dp, -1, sizeof(dp));
        memset(arr, 0, sizeof(arr));
        memset(path, false, sizeof(path));
    
        cin>> b >> k;
    for(int i = 1; i <= b; i++)
        cin>>arr[i];
    for(int i = 0; i < k; i++)
    {cin>> n >> m;
     path[n][m] = true;
    }
    
    cin >> e;
    cout << func(e) << endl;
    
    
    }
}