문제

형택이와 그의 친구들은 자꾸 다른 사람들이 대화를 엿듣는 것이 짜증났다. 따라서, 새로운 언어를 만들었다.

이 언어에는 단어가 N개 있다. 그리고 이 언어의 문장은 단어를 공백없이 붙여쓴 것이다. 이 문장에서 각 단어는 0번 또는 그 이상 나타날 수 있다. 이 언어가 형택스러운 이유는 (특별한 이유는) 단어에 쓰여 있는 문자의 순서를 바꿔도 되기 때문이다. 이때, 원래 단어의 위치와 다른 위치에 있는 문자의 개수 만큼이 그 순서를 바꾼 단어를 만드는 비용이다. 예를 들어, abc란 단어가 있을 때, abc는 비용 0으로 만들 수 있고, acb, cba, bac는 비용 2로 바꿀 수 있고, bca, cab는 비용 3으로 바꿀 수 있다.

따라서, 한 문장을 여러 가지 방법으로 해석할 수 있다. 이때 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문장이 주어진다. 문장의 길이는 최대 50이다. 둘째 줄에 단어의 개수 N이 주어지며, N은 50보다 작거나 같은 자연수이다. 셋째 줄부터 N개의 줄에 각 단어가 주어진다. 단어의 길이는 최대 50이다. 문장과 단어는 알파벳 소문자로만 이루어져 있다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 문장을 해석할 수 없다면 -1을 출력한다.

접근 과정

주어진 단어조합으로 입력된 문자열을 만들 수 있는지 확인하고 그 최소 비용을 구하는 문제이다. 온전한 단어로만 이루어진 문자열이었다면 무작정 비교하는식으로 풀 수 있었겠지만 문제는 문자열의 단어들의 순서가 뒤죽박죽 섞여있다.
우선은 두 문자열이 주어졌을 때 A문자열이 B문자열로 해석할 수 있는지를 판단하고 그 비용을 계산하는 함수 getTranslateCost()를 구현하였다. 두 문자열의 각 알파벳 갯수가 다르다면 해석할 수 없는 경우이다. 같다면 해석이 가능한 경우이므로 양 문자열에서 동일한 문자쌍을 이루지 못한 위치의 갯수가 문자가 이동해야하는 총 비용이 된다.
다음은 begin 에서 부터 시작되는 문자열을 wIndex번째 단어로 해석했을 때 필요한 최소비용을 구하는 함수 getMinCost()를 구현하였다. 맨 앞부분 부터 시작해 각 단어의 길이만큼만 해석하고 남은 문자열에 대해서 다른 단어로 해석할 수 있는지 재귀호출을 수행한다. begin부터 시작하는 문자열을 해당 단어로 해석할 수 없는 경우라면 비용으로 나올수 없는 큰 값인 inf를 반환한다.
여기까지는 아직 완전탐색으로 중복된 연산이 많아 시간초과가 발생할 수 있다. 메모이제이션 기법으로 getMinCost() 함수의 결과값을 캐싱하여 해결하였다. 결국 동적계획법 문제였다.

소스 코드

#include <cmath>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int inf = 1e7;

string sentence;
vector<string> words;
int cache[50][50];   //  [begin][word_Index]

int getTranslateCost(unsigned int begin, unsigned int wIndex) {
    string& original = words[wIndex];

    unsigned int end = begin + original.length();
    if (end > sentence.length()) { return -1; }    // 남은 문자가 단어의 길이보다 짧은 경우 해석 불가
    
    int cost = 0;
    int charCount[26] = {0, };

    // 각 알파벳의 갯수가 다르다면 해석 불가. 갯수가 동일하다면 위치가 다른 갯수가 총 비용이 된다.
    for (unsigned int i = 0; i < original.length(); ++i) { ++charCount[original[i] - 'a']; }
    
    for (unsigned int i = 0; i < original.length(); ++i) {
        char c = sentence[begin + i];
        if (c != original[i]) { ++cost; }
        --charCount[c - 'a'];
    }

    for (unsigned int i = 0; i < 26; ++i) {
        if (charCount[i] != 0) { return -1; }
    }
    
    return cost;
}

int getMinCost(unsigned int begin, unsigned int wIndex) {
    if (begin >= sentence.size()) { return 0; }        // 문장해석을 전부 마친 경우
    if (wIndex >= words.size()) { return inf; }    // 문장해석을 전부 마치지 못한 경우
    
    int& ret = cache[begin][wIndex];
    if (ret != -1) { return ret; }

    ret = inf;
    int cost = getTranslateCost(begin, wIndex);
    if (cost == -1) { return inf; }    // 해석이 불가능한 경우

    int nextBegin = begin + words[wIndex].length();
    for (unsigned int i = 0; i < words.size(); ++i) {
        ret = min(ret, getMinCost(nextBegin, i));
    }

    ret += cost;
    return ret;
}

int main() {
    int n;
    memset(cache, -1, sizeof(cache));

    cin >> sentence;
    cin >> n;
    words.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> words[i];
    }

    int minCost = inf;
    for (int i = 0; i < n; ++i) {
        minCost = min(minCost, getMinCost(0, i));
    }

    cout << (minCost < inf ? minCost : -1);
    return 0;
}