백준 1099번 알 수 없는 문장 - C++(cpp) 풀이

---

 

1. dp(idx): 부분 문자열 sentence[idx...]를 해석하는 최소 비용
2. dp(idx) = min(앞부분을 단어 word에 매칭 하는 비용 + dp(idx+word.size()))
3. 단어 매칭 비용 계산도 메모이제이션하여 시간을 절약한다.

 

1. dp(idx): 부분문자열 sentence[idx...]를 해석하는 최소 비용

 앞부분을 어느 단어와 매칭 시키느냐에 따라 뒷부분을 해석하는 비용이 달라지므로 다이나믹프로그래밍을 사용하여 구할 수 있다. dp(idx)를 위와 같이 정의하면, 총 구해야 하는 dp값은 문장의 길이와 같으므로 총 N=50개가 된다.

 

2. dp(idx) = min(앞 부분을 단어 word에 매칭 하는 비용 + dp(idx+word.size()))

 앞 부분을 단어로 매칭하고 나면 뒷부분은 다시 문장이 된다. 따라서 dp(idx) = 앞부분을 단어 word에 매칭 하는 비용 + dp(idx+단어 길이)이다. 매칭이 가능한 모든 단어들에 대해 이 값이 최소가 되는 것을 선택하면 된다.

 

3. 단어 매칭 비용 계산도 메모이제이션하여 시간을 절약한다.

 sentence의 idx번째 문자부터 단어 word를 매칭 시킬 수 있는지 확인하는 작업도 메모이제이션처리할 수 있다. 구해야 하는 값은 총 N^2개가 되고, 따라서 전체 시간 복잡도는 O(N^2)이다.

반응형

---

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

const int INF = 987654321;

int N;
string sentence, words[51];
int cache[51], check_cache[51][51];

// check(start_idx, word_idx): sentence[start_idx]부터 word_idx번 단어를 매칭시키는 비용
int check(int start_idx, int word_idx) {
    int& ret = check_cache[start_idx][word_idx];
    if (ret != -1) return ret;
    
    string word = words[word_idx];
    if (start_idx + word.size() > sentence.size()) return ret = INF;
    
    ret = 0;
    vector<int> alpha(26);  // 알파벳별 등장 횟수 기록
    for (int i=0; i<word.size(); i++) {
        int word_c = word[i] - 'a';
        int sentence_c = sentence[start_idx+i] - 'a';
        
        alpha[word_c]++;
        alpha[sentence_c]--;
        if (word_c != sentence_c) ret++;
    }
    
    for (int i=0; i<26; i++) {
        if (alpha[i] != 0) return ret = INF;
    }
    
    return ret;
}

// dp(idx) : 부분문자열 sentence[idx...]의 최소 비용
int dp(int idx) {
    if (idx >= sentence.size()) return 0;
    
    int& ret = cache[idx];
    if (ret != -1) return ret;
    
    // 모든 단어들에 매칭 시킨 뒤 최소 비용을 찾는다
    ret = INF;
    for (int i=0; i<N; i++) {
        int cost = check(idx, i);
        if (cost != INF) ret = min(ret, cost + dp(idx+words[i].size()));
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    memset(cache, -1, sizeof(cache));
    memset(check_cache, -1, sizeof(check_cache));
    
    cin >> sentence;
    cin >> N;
    for (int i=0; i<N; i++) cin >> words[i];
    
    int ans = dp(0);
    if (ans == INF) cout << -1;
    else cout << ans;

    return 0;
}