BOJ 1099 - 알 수 없는 문장 링크
(2024.03.20 기준 G3)

문제

하나의 문장과 $N$개의 단어가 주어진다. 문장은 단어를 공백없이 붙여쓴 것이며, 붙여쓸 때 단어는 각 문자의 순서를 바꿀 수 있다. 단, 원래 단어의 문자마다 위치가 다른 문자의 개수만큼 비용이 든다.

문장을 주어지는 $N$개의 단어로 해석할 때, 비용의 최솟값 출력

알고리즘

문자열 DP

풀이

$f(a, b)$는 문자열 $a$와 $b$에서 동일한 위치인데 다른 문자인 개수.
$g(s, i, j)$는 문자열 $s$의 $i$번째 인덱스부터 $j$번째 인덱스 직전까지의 부분 문자열.
$h(a, b)$는 문자열 $a$와 $b$의 이루어진 소문자의 종류와 개수가 같은지 판별.

모든 인덱스 $i$마다 증가하는 순서대로 살펴볼 때, $h(g(S, i-|word|, i), word)$를 만족하면 다음과 같은 점화식을 만족한다.
$dp(i) = min(dp(i), dp(i-|word|) + f(g(S, i-|word|, i), word))$

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const int MAX = 51;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string S; cin >> S;
    int N; cin >> N;
    vector<string> W(N); for (int i = 0; i < N; i++) cin >> W[i];

    /*
    f(a, b) : 동일한 위치인데 다른 문자인 개수 (|a| = |b|)
    g(s, i, j) : s의 i번째 인덱스부터 j번째 인덱스 직전까지의 부분 문자열
    h(a, b) : a와 b의 이루어진 소문자의 종류와 개수가 같은지 판별

    h(g(S, i-|word|, i), word)를 만족하면
    dp(i) = min(dp(i), dp(i-|word|) + f(g(S, i-|word|, i), word))
    */

    int dp[MAX], ct[26], res;
    bool valid;
    dp[0] = 0; fill(dp + 1, dp + MAX, -1);
    for (int i = 1, sz = S.size(); i <= sz; i++)
        for (string word: W)
            if (word.size() <= i && ~dp[i - word.size()]){ // 이을 수 있어야 한다.

                // h(g(S, i-|word|, i), word)를 만족하는지 확인
                fill(ct, ct + 26, 0);
                for (int j = 0, sz_ = word.size(); j < sz_; j++){
                    ++ct[S[i - sz_ + j] - 97];
                    --ct[word[j] - 97];
                }
                valid = true;
                for (int j = 0; j < 26; j++) if (ct[j]){
                    valid = false;
                    break;
                }
                if (!valid) continue;

                // f(g(S, i-|word|, i), word)를 구한다.
                res = 0;
                for (int j = 0, sz_ = word.size(); j < sz_; j++) if (S[i - sz_ + j] != word[j]) ++res;

                // dp(i) = min(dp(i), dp(i-|word|) + f(g(S, i-|word|, i), word))
                if (~dp[i]) dp[i] = min(dp[i], dp[i - word.size()] + res);
                // 현재 dp 값이 초기값일 경우
                else dp[i] = dp[i - word.size()] + res;
            }

    cout << dp[S.size()];
}

• Python

import sys; input = sys.stdin.readline

S = input().strip()
N = int(input())
W = [input().strip() for _ in range(N)]

'''
f(a, b) : 동일한 위치인데 다른 문자인 개수 (|a| = |b|)
g(s, i, j) : s의 i번째 인덱스부터 j번째 인덱스 직전까지의 부분 문자열
h(a, b) : a와 b의 이루어진 소문자의 종류와 개수가 같은지 판별

h(g(S, i-|word|, i), word)를 만족하면
dp(i) = min(dp(i), dp(i-|word|) + f(g(S, i-|word|, i), word))
'''

dp = [-1] * (len(S) + 1)
dp[0] = 0
for i in range(1, len(S) + 1):
    for word in W:
        if len(word) <= i and ~dp[i - len(word)]: # 이을 수 있어야 한다.

            # h(g(S, i-|word|, i), word)를 만족하는지 확인
            ct = [0] * 26
            for j in range(len(word)):
                ct[ord(S[i - len(word) + j]) - 97] += 1
                ct[ord(word[j]) - 97] -= 1
            valid = True
            for j in range(26):
                if ct[j]:
                    valid = False
                    break
            if not valid:
                continue

            # f(g(S, i-|word|, i), word)를 구한다.
            res = 0
            for j in range(len(word)):
                if S[i - len(word) + j] != word[j]:
                    res += 1

            # dp(i) = min(dp(i), dp(i-|word|) + f(g(S, i-|word|, i), word))
            if ~dp[i]:
                dp[i] = min(dp[i], dp[i - len(word)] + res)
            else: # 현재 dp 값이 초기값일 경우
                dp[i] = dp[i - len(word)] + res

print(dp[-1])