백준 1958번 LCS 3 - C++ 풀이

---

 

1. dp(a, b, c): A[a...], B[b...], C[c...]의 LCS 길이
2. 만약 A[a] = B[b] = C[c]이면,  dp(a, b, c) = 1 + dp(a+1, b+1, c+1)
3. 아니라면, dp(a, b, c) = max(dp(a+1, b, c), dp(a, b+1, c), dp(a, b, c+1))

 

1. dp(a, b, c): A[a...], B[b...], C[c...]의 LCS 길이

 세 문자열을 각각 A, B, C라고 하고 dp(a, b, c)를 위와 같이 정의하자.

 

2. 만약 A[a] = B[b] = C[c]이면,  dp(a, b, c) = 1 + dp(a+1, b+1, c+1)

 문자열 2개일 때 LCS와 똑같은 방식으로 점화식을 세우면 된다. 세 문자열의 첫 글자가 일치하면 해당 글자를 LCS에 포함 한 뒤 세 문자열 모두 다음 글자부터 탐색을 이어나가면 된다. 따라서 dp(a, b, c) = 1 + dp(a+1, b+1, c+1).

 

3. 아니라면, dp(a, b, c) = max(dp(a+1, b, c), dp(a, b+1, c), dp(a, b, c+1))

 세 문자열의 첫 글자가 일치하지 않으면 세 문자열 중 적어도 한 문자열의 첫 글자는 제외하고 다음 글자부터 탐색을 이어나가면 된다. 이때 LCS가 최대가 되는 방법을 택해야 한다. 따라서 max(dp(a+1, b, c), dp(a, b+1, c), dp(a, b, c+1))

반응형

---

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

using namespace std;

string A, B, C;
int cache[101][101][101];

// dp(a, b, c): A[a...], B[b...], C[c...]의 LCS 길이
int dp(int a, int b, int c) {
    if (a == A.size() || b == B.size() || c == C.size()) return 0;
    
    int& ret = cache[a][b][c];
    if (ret != -1) return ret;
    
    if (A[a] == B[b] && B[b] == C[c]) {
        ret = 1 + dp(a+1, b+1, c+1);
    }
    else {
        ret = 0;
        
        for (int i=0; i<2; i++) {
            for (int j=0; j<2; j++) {
                for (int k=0; k<2; k++) {
                    if (i == 0 && j == 0 && k == 0) continue;
                    ret = max(ret, dp(a+i, b+j, c+k));
                }
            }
        }
    }

    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    memset(cache, -1, sizeof(cache));
    
    cin >> A >> B >> C;
    cout << dp(0, 0, 0);

    return 0;
}