[BOJ/백준][Gold3] 1099 : 알 수 없는 문장 (C++)

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

1099번: 알 수 없는 문장

 

 

[난이도] Gold3
[유형] DP

[풀이]
단어의 개수와 길이가 50으로 작기 때문에 다이나믹 프로그래밍으로 해결이 가능합니다.

dp 배열은 다음과 같이 정의가 가능하며
dp[n] : 문장 string을 s라고 했을 때, s[n~s.size()-1] 인 substring을 해석하기 위해 필요한 최소 연산

점화식은 다음과 같습니다.
dp[n] = dp[i+1] + [s[n~i]인 substring을 해석하는데 필요한 cost] ( n<=i<s.size()-1)

모든 N개의 단어를 substring s[n~i]으로 변환하는데 드는 cost 중 최솟값을 위의 cost로 사용하면 됩니다.
아래 코드에서는 일단 비교하는 두 string을 정렬하여 비교함으로써 정확히 같은
문자들을 가지고 있는지 확인하였고, 원본 string을 다시 비교하면서 위치가 다른 문자들의 개수를 세서
전체 문자 길이에서 빼주었습니다.

 

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
string s,word[50];
int dp[51],N,inf=9e8;
int cost(string a,string b){
    if(a.size()!=b.size()) return inf;
    string ta = a;
    string tb = b;
    sort(ta.begin(),ta.end());
    sort(tb.begin(),tb.end());
    if(ta!=tb) return inf;

    int ret = a.size();
    for(int i=0;i<a.size();i++){
        if(a[i]==b[i]) ret--;
    }
    return ret;
}
int minCost(string k){
    int ret = inf;
    for(int i=0;i<N;i++) ret = min(ret,cost(k,word[i]));
    return ret;
}
int sol(int n){
    if(n==s.size()) return 0;
    int& ret = dp[n];
    if(ret!=-1) return ret;
    ret = inf;
    for(int i=n;i<s.size();i++){
        string k = s.substr(n,i-n+1);
        int c = minCost(k);
        if(c==inf) continue;
        ret = min(ret,c+sol(i+1));
    }
    return ret;
}
int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    cin >> s >> N;
    for(int i=0;i<N;i++) cin >> word[i];
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0)==inf ? -1 : sol(0));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/1099.cpp