[백준] 9252 : LCS 2

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

9252번: LCS 2

---

• LCS 1 문제와 똑같지만, 이번엔 단순히 LCS 의 길이가 아닌 해당 문자열까지 출력하는 문제이다.
• 기존에 사용하던 길이를 저장하던 DP 배열을, 문자열을 저장하게끔 하면 똑같은 방식으로 풀 수 있다.
• 그러나 string 배열을 1000 x 1000 개 사용하기 때문에 조금 불편한데, 문자열을 전부 저장하지 않고 길이에 대한 DP 배열을 그대로 가져간 뒤에, 마지막 지점부터 LCS 가 지정된 과정을 추적할 수 있다.
• LCS 를 가져올 때 (문자가 다를 경우) 왼쪽에서 가져오는지 위쪽에서 가져오는지에 대한 배열을 따로 저장한 뒤, 마지막 지점부터 시작해 아래 노란색 경로처럼 역추적한다.

노란색 경로를 따라감

---

#include <iostream>
#include <string>

using namespace std;

string s1, s2;
string answer[1001][1001];

int main(void)
{
    cin >> s1 >> s2;

    for(int r = 0 ; r < s2.size() ; r++)        // answer[r][c] 는 s2[0:r] 과 s1[0:c] 까지의 LCS
    {
        for(int c = 0 ; c < s1.size() ; c++)
        {
            if(s2[r] == s1[c]) answer[r+1][c+1] = answer[r][c] + s1[c];         // 같은 문자가 나올 경우 이번 문자가 추가되기 이전 문자열들의 LCS 에 이번 문자를 더해줌
            else answer[r+1][c+1] = (answer[r][c+1].size() > answer[r+1][c].size() ? answer[r][c+1] : answer[r+1][c]);  // 다른 문자라면 현재까지의 LCS 중 최대 길이의 LCS 를 선택
        }
    }

    cout << answer[s2.size()][s1.size()].size() << endl;
    if(answer[s2.size()][s1.size()].size())
        cout << answer[s2.size()][s1.size()] << endl;
}