[ 백준 BOJ ] 1099번 - 알 수 없는 문장 (C++)

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

 

생각 흐름

• 문제 예제를 보자마자 떠오른 예외 케이스는 abcd, bca, abcd와 같이 주어졌을 때이다. 이 케이스를 떠올리자마자 그리디적으로 접근하면 무조건 틀리겠다고 생각했다.
• 다른 방법이 안 떠올라 dp로 접근해보기로 했다.
• 문제가 풀리게끔 점화식을 생각해보니 dp[i] = dp[a] + b와 같이 할 수 있을 거 같았다. a의 경우는 0부터 i-1까지의 값을 가지고, b의 경우 a 이후의 값부터 i까지에서 가장 적은 비용의 단어를 찾아주면 된다.
• 즉, abcd가 있고 i가 3(d)일 때 0부터 3까지의 단어가 있는지 찾아주고, 이후 dp[0] + bcd, dp[1] + cd, dp[2] + d 중에서 가장 작은 값을 저장하면 된다.
• 성공

#include <iostream>
#include <vector>
#include <string>
#include <memory.h>
#include <unordered_map>
#include <cmath>

using namespace std;

string s;
int N;
vector<string> v[51];


int findAll(int i, int j){
    if(v[j-i+1].empty()) return 987654321;
    
    unordered_map<char, int> p;
    
    for(int k = i; k<=j; k++){
        p[s[k]]++;
    }
    
    int minCost = 987654321;
    
    for(int k = 0; k<v[j-i+1].size(); k++){
        int cost = 0;
        int reminder = j - i + 1;
        
        unordered_map<char, int> m = p;
        
        for(int h = i; h<=j; h++){
            if(m[v[j-i+1][k][h-i]]>0){
                m[v[j-i+1][k][h-i]]--;
                reminder--;
                if(s[h] != v[j-i+1][k][h-i]){
                    cost++;
                }
            }else{
                cost = 987654321;
                break;
            }
        }
        if(reminder>0) continue;
        minCost = min(minCost, cost);
    }
    
    return minCost;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>s;
    cin>>N;
    
    for(int i = 0; i<N; i++){
        string tmp;
        cin>>tmp;
        
        v[tmp.size()].push_back(tmp);
    }
    
    int dp[50];
    
    for(int i = 0; i<50; i++){
        dp[i]=987654321;
    }
    
    for(int i = 0; i<s.size(); i++){
        dp[i] = min(dp[i], findAll(0, i));
        for(int j = 0; j<i; j++){
            if(dp[j]==987654321) continue;
            dp[i] = min(dp[i], dp[j]+findAll(j+1, i));
        }
    }
    
    if(dp[s.size()-1] == 987654321) cout<<-1<<endl;
    else cout<<dp[s.size()-1]<<endl;
    
    return 0;
}