[백준 C++] 9252번 LCS 2

9252번: LCS 2

문제 요약

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

사용 알고리즘

다이나믹 프로그래밍

입출력

• 입력: 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
• 출력: 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다. LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다. ``` 예제1

입력 ACAYKP CAPCAK 출력 4 ACAK

## 풀이
LCS를 활용하는 문제이다 2차원으로 dp를 짜서 풀면 된다. 이번엔 겹치는 문자열까지도 출력해야하는데 끝에서 역순으로 따라가면 된다. 2차원 dp에서 i번째와 j번째의 문자열이 같다면 왼쪽 위 대각선으로 이동하면서 s에 문자를 추가하고 다르면 왼쪽과 위중 더 큰곳으로 이동한다. 이후 s의 역순으로 문자열을 출력하면 된다.

## 어려웠던 점
lcs를 풀었었는데도 헷갈렸다. 문자열 역순 탐색은 검색을 해서 알아냈다.

## 배운 점 / 느낀 점
lcs를 완전히 이해했다. 나중에 또 까먹을수도 있지만 잘 기억해 두어야 겠다.

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

string s1, s2;
vector<vector<int>> dp;
vector<char> s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> s1 >> s2;
    dp = vector<vector<int>>(s1.size() + 1, vector<int>(s2.size() + 1, 0));

    for (int i = 1; i < s1.size()+1; i++) {
        for (int j = 1; j < s2.size()+1; 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.size();
    int j = s2.size();
    while(i!= 0 && j != 0){
        if(s1[i-1] == s2[j-1]){
            s.push_back(s1[i-1]);
            i--;
            j--;
        }
        else{
            if(dp[i-1][j] > dp[i][j-1]){
                i--;
            }
            else{
                j--;
            }
        }
    }
    if(s.size() == 0){
        cout << 0;
        return 0;
    }
    else{
        cout << s.size() << '\n';
        for (int i = s.size()-1; i >= 0; i--) {
            cout << s[i];
        }
    }

    return 0;
}