BOJ)1856 단어 게임

문제: icpc.me/1856

w개의 문자열이 주어진다.

길이 l의 문자열을 앞서 주어진 w개의 문자열로만 표현하고 싶을 때 지워야하는 문자의 최소 개수를 출력하는 문제이다.

dp[x]=길의 l의 문자열을 길이 x까지 봤을 때 지워야하는 최소 문자의 수

로 정의한 뒤 점화식을 세우면

dp[x]를 채우기 위해선 w개의 각각의 문자열에 대해서 저 문자를 남기기 위하여 지워야할 개수를 구해주면 

l*l*w의 시간복잡도로 디피 테이블을 채울 수 있다.

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <cstring>
using namespace std;
int w,l,dp[333];
string s[666];
string t;
int func(int here){
    if(here<0)return 0;
    int &ret=dp[here];
    if(ret!=-1)return ret;
    ret=here+1;
    for(int i=0;i<w;i++){
        string &curr=s[i];
        int len=(int)curr.length();
        int it=here;
        int flag=1;
        for(int j=len-1;j>=0;j--){
            while(it>=0&&t[it]!=curr[j])it--;
            if(it<0)flag=0;
            it--;
        }
        if(flag)ret=min(ret,func(it)+here-it-len);
    }
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>w>>l;
    cin>>t;
    for(int i=0;i<w;i++)
        cin>>s[i];
    memset(dp,-1,sizeof(dp));
    cout<<func(t.length()-1);
    return 0;
}