백준 9252 LCS 2 (C++)

9252번: LCS 2

dp를 이용한 문제이다. 먼저 dp를 이용해 LCS를 구해준다. 두 문자열을 반복문을 돌며 비교하여 문자가 같을 경우 1씩 더해가며 dp를 구해주었다. 그 후 dp를 역추적해 LCS를 구해준다. 같은 문자인 경우 1을 더해주었으므로 dp에서 위, 아래에 같은 값이 없을 경우 같은 문자이기에 1을 더해준 것으로 판단하여 해당 위치의 문자를 result에 더해주었다. 이를 반복하여 값을 구하고 길이와 값을 출력해주었다. LCS 길이를 구하는 알고리즘은 이전에 푼 적이 있어서 쉽게 생각해낼 수 있었는데 역추적을 하는 과정에서 좀 해맸었다. 처음에는 dp를 string으로 해서 길이를 구하는 과정을 문자를 저장해주는 방식으로 바꾸어봤었는데 시간 초과가 났었다. 그래서 기존 방식을 그대로 두고 역추적하는 방식을 생각해냈다. dp 문제를 더 많이 풀어봐야 겠다.

#include <iostream>
#include <algorithm>

using namespace std;

string s1, s2;
int dp[1001][1001];
string result;

void findResult(int y, int x) {
    if (!dp[y][x]) return;

    if (dp[y][x] == dp[y - 1][x]) {
        findResult(y - 1, x);
        return;
    }
    else if (dp[y][x] == dp[y][x - 1]) {
        findResult(y, x - 1);
        return;
    }

    result = s1[y - 1] + result;
    findResult(y - 1, x - 1);
}

void solution() {
    for (int i = 0; i < s1.size(); i++) {
        for (int j = 0; j < s2.size(); j++) {
            if (s1[i] == s2[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
            }
            else {
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
            }
        }
    }

    findResult(s1.size(), s2.size());

    cout << dp[s1.size()][s2.size()] << "\n";
    cout << result;
}

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

    cin >> s1;
    cin >> s2;

    solution();

    return 0;
}