백준 5188 - Biomedical Engineering

문제 링크 : https://www.acmicpc.net/problem/5188

m개의 문자열을 이어붙여서
z라는 문자열 만들면 되는 문제이다

dp[idx] 선언했는데 이는

z의 현재 idx 이후에 문자열을 이어붙일 때
필요한 최소의 이어붙이는 횟수로 정의했다.

dp[idx]는 idx기준 뒤의 것의 카운트만 신경쓴다는 점을
잘 캐치하고 상태전이?를 생각해보면 될 것 같다.

#include<iostream>
#include<algorithm>
#include<vector>
const int INF = 1e9;
using namespace std;
vector<string> v;string z;
int dp[1010];
int sol(int idx){
    if(idx==z.length()){
        return 0;
    }
    int & ret = dp[idx];
    if(ret!=-1) return ret;
    ret = INF;
    for(int i=0;i<v.size();i++){
        string a = v[i];
        if(idx+a.length()<=z.length()){
            string b = z.substr(idx,a.length());
            if(a==b){
                ret=min(ret,sol(idx+b.length())+1);
            }
        }
    }
    return ret;
}
int main(){
    int T;cin>>T;int idx = 0;
    while(T){
        T--;idx++;
        v.clear();fill(dp,dp+1010,-1);
        int m;cin>>m;
        cin>>z;
        for(int i=0;i<m;i++){
            string a;cin>>a;v.push_back(a);
        }
        int ans = sol(0);
        cout<<"Data Set "<<idx<<":"<<"\n";
        if(ans==INF) cout<<"Impossible"<<"\n";
        else cout<<ans<<"\n";
    }
}