[백준 1856] 단어 게임

문제

https://www.acmicpc.net/problem/1856

 

알고리즘

DP

 

풀이

주어진 문자열을 단어 리스트를 조합하여 만들기 위한 최소 제거 횟수를 묻는 문제입니다.

 

2차원 배열의 구간DP를 선언하여 $i~j$까지 만들기 위한 최소 제거 횟수를 구하여 풀었지만 2차원 배열 대신 1차원 배열로도 풀 수 있습니다. 주어진 단어 w를 사용할 때, 중간에 끊는 것 없이 한번 사용하면 무조건 끝까지 매칭하여야 하기 때문입니다.

 

cache[i] = 문자열 S의 $i$번째까지 만들기 위한 최소 제거 횟수

 

주어진 단어 w를 전부 매칭했다면 (idx값이 -1) 제거한 문자 수를 계산하여 cache값을 업데이트하면 됩니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int w, l, cache[305];
string s, word[605];

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> w >> l;
    cin >> s;
    rep(i, w) {
        cin >> word[i];
    }

    rep(i, l) {
        cache[i] = i + 1;

        rep(j, w) {
            int idx = (int)word[j].length() - 1;
            for (int k = i; k >= 0; --k) {
                if (s[k] == word[j][idx]) {
                    --idx;
                    if (idx == -1) {
                        cache[i] = min(cache[i], (k == 0 ? 0 : cache[k - 1]) + (int)(i + 1 - k - word[j].length()));
                    }
                }
            }
        }
    }
    cout << cache[l - 1];
    return 0;
}