[LCS] 백준 9251 LCS / 9252 LCS2 C++

 

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

9251번: LCS

9251 LCS길이

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string str1, str2;
int lcs[1001][1001];

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

    str1 = "0" + str1;
    str2 = "0" + str2;

    for (int i = 0; i < str1.size(); i++) {
        for (int j = 0; j < str2.size(); j++) {
            if ((i == 0) || (j == 0)) {
                lcs[i][j] = 0;
                continue;
            }

            if (str1[i] == str2[j]) lcs[i][j] = lcs[i - 1][j - 1] + 1;
            else {
                if (lcs[i - 1][j] > lcs[i][j - 1]) lcs[i][j] = lcs[i - 1][j];
                else lcs[i][j] = lcs[i][j - 1];
            }
        }
    }
    cout << lcs[str1.size() - 1][str2.size() - 1];
    return 0;
}

 

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

9252번: LCS 2

 

9252 LCS 길이, LCS 역추적

#include<iostream>
#include<string>
using namespace std;

string str1;
string str2;
string ans;
int dp[1001][1001];
int n1, n2, res, a, b;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> str1 >> str2;
    // 문자열 길이 다를 수 있음
    n1 = str1.size();
    n2 = str2.size();
    // 인덱스 접근 편하게
    str1 = "0" + str1;
    str2 = "0" + str2;

    // base = 0은 0으로 초기화
    for (int i = 0; i <= n1; i++)
    {
        for (int j = 0; j <= n2; j++)
        {
            if ((i == 0) || (j == 0))
            {
                dp[i][j] = 0;
                continue;
            }

            if (str1[i] == str2[j])   // dp table 대각선 + 1
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else  // dp table 위, 왼쪽 중 큰 값
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    res = dp[n1][n2];
    a = n1;
    b = n2;
    while (dp[a][b] != 0)
    {
        if ((dp[a][b] == dp[a - 1][b]))
        {
            a--;
        }
        else if ((dp[a][b] == dp[a][b - 1]))
        {
            b--;
        }
        else
        {
            ans.insert(0, 1, str1[a]);  // push_back, append X 반대로
            a--;
            b--;
        }
    }

    cout << res << "\n";
    cout << ans;
}