[백준 16500번] [동적 계획법] 문자열 판별

Approach

이 문제를 완전탐색으로 접근해보면, 앞에서부터 모든 문자열에 대해서 되는지를 체크해주면 된다.

다만, 비둘기집의 원리에 의해서 중복되는 계산이 매우 많다는 사실을 캐치할 수 있다.

 

이 지점에서 Memoization을 활용한 DP를 활용해서 중복되는 계산을 줄일 수 있음을 생각할 수 있다.

dp[i] : s의 i 번쨰 index까지는 매핑되었고, 그 이후의 문자열을 매칭지을 수 있는지 여부 (가능하면 1, 아니면 0)

dp[i] = max(dp[i + v[j].size()]) for all j s.t s.substr(i, i + v[j].size()) == v[j] (v[j] 는 j번째 문자열)

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int dp[101];
vector<string> v;
string s;
int n;

int memoi(int k){
    int& ret = dp[k];
    if(k == s.size()) return ret = 1;
    if(ret != -1) return ret;
    for(int i = 0; i < n; i++){
        if(k + v[i].size() > s.size()) continue;
        bool flag = true;
        for(int j = 0; j < v[i].size(); j++){
            if(s[k + j] != v[i][j]){
                flag = false;
                break;
            }
        }
        if(flag){
            if(memoi(k + v[i].size())) return ret = 1;
        } 
    }
    return ret = 0;
}

int main(void){
    memset(dp, -1, sizeof(dp));
    cin >> s;
 
    cin >> n;
    for(int i = 0; i < n; i++){
        string t;
        cin >> t;
        v.push_back(t);
    }

    cout << memoi(0) << "\n";
    return 0;
}