[백준 9252] LCS 2 C++

www.acmicpc.net/problem/9252

9252번: LCS 2

 

 

 

LCS 2는 LCS 1를 응용한 문제입니다.

 

LCS 2를 풀기위해서, LCS 1의 과정을 이해해야합니다.

rolypolytoy.tistory.com/43?category=365766

[백준 9251] LCS C++

 

 

LCS 1을 이해하셨다면, LCS 2는 문자열을 찾는 알고리즘을 삽입하면 됩니다.

 

찾는 알고리즘은 LCS 1을 구현한 것을 반대로 재귀 호출을 한다음, return 하면서 해당하는 문자 값을 출력하시면 됩니다.

 

LCS 1에서 a[i-1] == b[j-1]이라면 dp[i][j] = d[i-1][j-1] + 1 (1의 의미는, 공통 문자 하나 찾았다는 의미)

으로 구했기 때문에, 반대로,

i, j의 인덱스가 dp[i][j] 위치에 있을 때,

a[i-1] == b[j-1] 의 조건이 만족이 된다면, a[i-1][j-1]이 공통 부문 문자열 중 하나이기 때문에 그 칸으로 다시 재귀 호출을 합니다.

 

a[i-1] != b[j-1]의 경우, LCS를 구할 때 dp 배열의 왼쪽, 위쪽 배열 중 최댓값을 취했기 때문에,

반대로 문자열을 찾아갈 때도, dp의 왼쪽, 오른쪽 중에 최대값으로 다시 재귀호출을 하여 찾아가면됩니다. 

 

그렇게 되면 재귀호출은 항상 a[i-1] == b[j-1]에서 모든 호출이 끝나고 난 뒤에,

a[i-1]이나 b[j-1]을 호출하게 된다면, return으로 반환하면서 우리가 찾고 싶어하는 LCS의 문자열을 찾을 수 가 있습니다.

저한테 DP 사용과 재귀호출로 반대로 찾아가는 것이 처음에 어렵다고 느껴졌습니다. 하지만, 왜 이런 결과가 나왔는지에 대해

차근차근 생각해보고 다른 블로그나 개념들을 읽어보면서 이해하시면 개념이 조금씩 보이기 시작한다고 생각합니다.

 

오늘도 좋은 하루 되세요^^ 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

const int MAX = 1001;

int dp[MAX][MAX];

string a, b;
void find(int i, int j){
    if (dp[i][j] == 0) return; // LCS 값이 없을 땐 출력하지 않기

    if (a[i-1] == b[j-1]){ // 이전의 문자가 같다면, 해당 인덱스로 재귀호출하기
        find(i-1, j-1);
        cout << a[i-1]; // a[i-1] 혹은 b[i-1] 둘 중 하나 출력하기
    } else dp[i-1][j] > dp[i][j-1] ? print(i-1, j) : print(i, j-1);
    // a, b중에서 LCS가 더 큰 값으로 재귀함수 호출하기
}
void solution(){

    
    cin >> a >> b;

    int a_size = a.length();
    int b_size = b.length();

    for (int i = 1; i <= a_size; i++)
        for (int j = 1; j <= b_size; j++){
            if (a[i-1] == b[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
	// LCS 1처럼 LCS 값 찾기
    

    cout << dp[a_size][b_size] << '\n';
    
	// a_size, b_size위치부터 거꾸로 문자를 찾아가기.
    find(a_size, b_size);
}
int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solution();

    return 0;
}