백준 9252번

LCS2 문제로 LCS(Sequence)의 값과 더불어 문자열까지 출력하는 문제입니다.

LCS를 찾는 dp배열에서 문자열을 저장해두면 되지 않을까 생각했는데 생각만으로 끝냈습니다.

구현은 LCS를 찾기 위해 진행된 반복문을 역순으로 추적해서 문자를 스택에 넣고(역순으로 출력해야되기 때문에) 빼면서 출력했습니다.

#include <cstdio>
#include <cstring>
#include <stack>
 
int max(int a, int b) {
    return a > b ? a : b;
}
 
int main() {
    char str1[1001];
    char str2[1001];
    scanf("%s", &str1);
    scanf("%s", &str2);
    int size1 = strlen(str1);
    int size2 = strlen(str2);
 
    int** dp = new int*[size1 + 1];
    for (int i = 0; i <= size1; i++) {
        dp[i] = new int[size2 + 1]();
    }
 
    int lcs = 0;
    for (int i = 1; i <= size1; i++) {
        for (int j = 1; j <= size2; j++) {
            if (str1[i - 1] == str2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    printf("%d\n", dp[size1][size2]);
 
    int i = size1;
    int j = size2;
    std::stack<char> lcsStr;
    while (i > 0 && j > 0) {
        if (dp[i][j] == dp[i - 1][j]) {
            i--;
        }
        else if (dp[i][j] == dp[i][j - 1]) {
            j--;
        }
        else {
            lcsStr.push(str1[i - 1]);
            i--;
            j--;
        }
    }
    while (!lcsStr.empty()) {
        printf("%c", lcsStr.top());
        lcsStr.pop();
    }
}