[백준/C++] 9252번: LCS 2

문제 & 링크

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

풀이

1. dp 테이블을 0으로 초기화한다.

2. 두 문자열을 dp 테이블의 1부터 시작하도록 반복문을 설정한다.

3. 각 문자열의 원소가 같을 경우 dp[i][j]라면 dp[i-1][j-1]에서 1을 더해서 저장한다. 대각선의 값에서 1을 더하는 이유는 각 문자열에서 i번째 j번째 문자가 빠졌을 때 i-1번째, j-1번째 까지의 공통 부분 수열이 1 줄어야 하기 때문이다.

4. 각 문자열의 원소가 다를 경우 dp[i][j]라면 dp[i-1][j]와 dp[i][j-1] 중 큰 값을 저장한다.

5. 3 - 4의 과정을 반복하며 dp 테이블의 마지막 원소에서 LCS의 길이를 구할 수 있다.

6. dp 테이블의 마지막 원소(LCS의 길이)로부터 역으로 추적하여 LCS의 길이가 0이 될 때 까지의 경로를 구한다.

7. 만약 현재 위치인 dp[i][j]와 dp[i-1][j-1]이 같은 값이라면 dp[i-1][j-1]로 이동한다.

8. 만약 7의 조건을 만족하지 않지만 dp[i-1][j] 또는 dp[i][j-1]와 같은 값이라면 해당 위치로 이동한다.

9. 7과 8의 조건을 모두 만족하지 않는다면 dp[i-1][j-1]로 이동하며 해당 문자열의 인덱스에 해당하는 문자를 저장한다.

10. 7 - 9의 과정을 반복하며 dp 테이블의 원소가 0이 될 경우 LCS를 구할 수 있다.

참고 자료

코드

#include <iostream>
#include <string>

using namespace std;

int dp[1001][1001] = {0};

int main() {
    string S1, S2;
    string ans = "";
    
    cin >> S1;
    cin >> S2;
    
    for (int i = 1; i <= S1.length(); i++) {
        for (int j = 1; j <= S2.length(); j++) {
            if (S1[i - 1] == S2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); 
        }
    }
    
    
    int i = S1.length(), j = S2.length();
    while (dp[i][j] != 0) {
        if (dp[i - 1][j - 1] == dp[i][j]) {
            i--;
            j--;
        }
        else if (dp[i - 1][j] == dp[i][j]) i--;
        else if (dp[i][j - 1] == dp[i][j]) j--;
        else {
            ans = S1[i - 1] + ans;
            i--;
            j--;
        }
    }
    
    cout << dp[S1.length()][S2.length()] << "\n";
    if (dp[S1.length()][S2.length()] != 0) cout << ans;
    
}