BOJ 9252 LCS 2

1 개요

BOJ 9252 LCS 2

• 백준 온라인 저지 9252번 문제
• BOJ 34단계

2 C++

#include <bits/stdc++.h>
using namespace std;

string s1, s2;
int dp[1001][1001] = {};
string answer;

void solve() {
    for(int i=0; i<s1.length(); i++) {
        for(int j=0; j<s2.length(); j++) {
            if(s1[i] == s2[j]) {
                dp[i+1][j+1] = dp[i][j] + 1;
            } else {
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
            }
        }
    }
    int i=s1.length()-1;
    int j=s2.length()-1;
    while(i>=0 && j>=0) {
        if(dp[i+1][j+1] == dp[i][j+1]) {
            i--;
        } else if(dp[i+1][j+1] == dp[i+1][j]) {
            j--;
        } else {
            answer += s1[i];
            i--;
            j--;
        }
    }
}

int main() {
    cin >> s1 >> s2;
    solve();
    cout << dp[s1.length()][s2.length()] << '\n';
    for(int i=answer.size()-1; i>=0; i--) {
        cout << answer[i];
    }
}