백준 10719 Baekjoon Database Management System

https://boj.ma/10719/t 

10719번: Baekjoon Database Management System

 

 

문제 설명은 생략합니다

 

i번째로 읽어야 할 데이터에 대해 선택지가 여러개 있습니다

Area1에 저장된 데이터가 이번에 읽어야 할 데이터와 같다면, 아무 비용도 내지 않고 읽고 넘어가기.

다르다면, i번째 데이터를 c원 내고 저장소에 저장하고 읽고 넘어가기 혹은 저장소는 그대로 두고 i번째 데이터를 읽는 비용을 내고 넘어가기 이렇게 분기가 나누어 질것입니다.

 

완전탐색으로 모든 경우를 해보면 답을 찾을 수 있을것 같습니다.

하지만 n <= 10^5 으로 모든 i번째마다 경우에 따라 분기한다면 지수함수처럼 경우의수가 증가할 것 같습니다.

당연히 시간초과입니다.

 

모든 경우를 보는것이 오래걸리니, 안 봐도 되는 경우에 대해 생각해봤습니다.

예제를 그대로 들고와보면

10 3 5
2 2 4
1 1 1 1 1 2 2 2 3 2

 

9번째 데이터에 3이 처음 나오는데 9번째 데이터를 읽어야 한다고 생각해봅니다, 저장소에는 2가 저장되어있다고 생각해봅니다.

 

현재 9번째 데이터를 읽어야 하고, 저장된 데이터가 2일때 n번째 데이터까지 읽는 최소비용 을 알고싶은건데

9번째 이전까지 어떻게 선택했든, 저장소에 2가 있다면 3을 새로 저장하지 않고 3을 읽는 비용 4원을 내고 마지막 2를 읽고

끝내는게 최소인 것은 항상 똑같을 것입니다.

앞에서 어떻게 다르게 선택하고 9번째까지 오고 저장소에 데이터가 2가 있으면, 최소비용은 항상 일정합니다.

그렇다면 한 번 본 경우는 굳이 다시 안봐도 되겠지요. 따라서 dp로 최적화가 가능합니다.

 

i번째 데이터를 읽어야 하고 j번 데이터가 저장돼있을때 로 재귀함수를 정의합니다

recur(cur, save)

cur에는 1 ~ n번째 데이터까지 들어갈 수 있고

save에는 최대 1~m개의 데이터를 저장할 수 있습니다.

dp배열에 dp[cur][save]상태를 저장할 것이므로 N*M사이즈의 dp배열이 필요합니다.

이 dp배열을 채울것이므로 총 시간복잡도는 O(NM)이 되어 시간내에 통과 가능합니다.

 

또

"i번째로 읽어야 할 데이터에 대해 선택지가 여러개 있습니다

Area1에 저장된 데이터가 이번에 읽어야 할 데이터와 같다면, 아무 비용도 내지 않고 읽고 넘어가기.

다르다면, i번째 데이터를 c원 내고 저장소에 저장하고 읽고 넘어가기 혹은 저장소는 그대로 두고 i번째 데이터를 읽는 비용을 내고 넘어가기 이렇게 분기가 나누어 질것입니다."

 

이 선택지로 만들어지는 상태들에 대해 그래프로 표현한다면 DAG가 만들어지기 때문에 dp를 적용할 수 있다는것을 알 수 있습니다.

 

 

코드 (c++)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define NM 101010
#define MAX 1010100
#define BIAS 1048576
#define MOD 1000000007
#define X first
#define Y second
#define INF 100000000
#define FOR(i) for(int _=0;_<(i);_++)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
using namespace std;
// pbds
//using namespace __gnu_pbds;
//// multi-set
//using ordered_set_equal = tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>;
//// set
//using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;


int main() {
    fastio
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t;
    cin >> t;
    while(t--){
        int n, m, c;
        cin >> n >> m >> c;
        vector<int> data(m + 1), arr(n);
        for (int i = 1; i <= m; i++) cin >> data[i]; // i번 데이터를 읽는 비용
        
        for (int&a : arr) cin >> a; // 읽어야 할 데이터 순서
        
        vector<vector<int>> dp(n, vector<int>(31, -1));
        
        auto recur = [&](const auto&self, int cur, int save){
            if (cur == n) return 0;
            int&ret = dp[cur][save];
            if(~ret) return ret;
            ret = INF;
            if (save == arr[cur]){ // 저장소에 저장된거랑 이번에 읽을거랑 똑같음
                ret = min(ret, self(self, cur + 1, save)); // 비용 안내고 읽고 넘어가기
            }else{ // 저장소랑 현재 데이터랑 다름
             	// 저장소 유지하고 비용 내고 넘어가기
                ret = min(ret, self(self, cur + 1, save) + data[arr[cur]]);
                // 저장소에 현재 데이터 저장하고 저장비용 내고 넘어가기
                ret = min(ret, self(self, cur + 1, arr[cur]) + c); 
            }
            return ret;
        };
        
        cout << recur(recur, 0, 0) << endl;
    }
    return 0;
}