백준 1856, DP
USACO February 2007 Contest Silver 1번 문제.
$ dp[x] $ 는 $x$ 번째 글자부터 문자열을 완성하기 위해 제거해야 하는 문자의 최솟값이다.
주어진 문자열 $S$ 의 $x$ 번째 글자 $S[x]$ 가 있을때,
$S[x]$ 와 첫 글자가 일치하는 단어 $w$ 들을 찾아서, 단어를 완성 시킬 수 있는 지점 $y$ 를 찾는다.
제거 해야하는 문자의 수는 $y - x - w.size() + 1$ 이다.
$dp[x] = dp[y + 1] + (y - x - w.size() + 1)$
을 만족하는 가장 작은 $dp[x]$ 를 구하면 된다.
Source Code
//BOJ1856
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
int W, L;
string S;
vector<string> wordlist(666);
int cache[333];
int makeword(int pos, string word) {
//word 를 완성시킬 수 있는 위치 pos 를 return.
int chk = 0, ret = -1;
for (int i = pos; i <= S.size(); ++i) {
if (S[i-1] == word[chk]) ++chk;
if (chk == word.size()) {
ret = i;
break;
}
}
return ret;
}
int dp(int here) {
if (here > L) return 0;
if (here == L) return 1;
int& ret = cache[here];
if (cache[here] != 1234) return ret;
for (int i = 1; i <= W; ++i) {
string w = wordlist[i];
if (w[0] != S[here - 1]) continue;
int p = makeword(here, w);
if (p == -1) continue;
int tmp = dp(p + 1) + (p - here - w.size() + 1);
ret = min(ret, tmp);
}
ret = min(ret, dp(here + 1) + 1);
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> W >> L;
cin >> S;
for (int i = 1; i <= W; ++i) {
cin >> wordlist[i];
}
for (int i = 0; i < 333; ++i) {
cache[i] = 1234;
}
printf("%d\n", dp(1));
return 0;
}