백준 9252 LCS 2 c++ (dp)

문제 출처 : https://www.acmicpc.net/problem/9252

9252번: LCS 2

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

알고리즘 분류

• 다이나믹 프로그래밍
• 문자열

풀이

이전에 풀었던 백준 9251 LCS 문제는 LCS의 길이만 출력하면 됐는데,

LCS도 같이 출력하라는 조건이 추가된 문제로, 이전과 같은 로직으로 풀 수 있다. 

https://ongveloper.tistory.com/36

백준 9251 LCS c++

위의 문제를 풀면, LCS의 길이를 알 수 있다.

같은 방법으로, 비교하는 문자가 같을 땐, 왼쪽 대각선 위의 LCS에 현재 문자를 추가해 주고,

비교하는 문자가 다를 땐, 왼쪽과 위의 LCS 중, 길이가 긴 것을 선택해 저장한다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int dp[1001][1001];
string lcs[1001][1001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string str1,str2;

    cin >> str1 >> str2;

    for (int i = 1; i <= str1.length(); i++) {
        for (int j = 1; j <= str2.length(); j++) {
            if (str1[i-1] == str2[j-1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                lcs[i][j] = lcs[i - 1][j - 1] + str1[i-1];
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                lcs[i][j] = (lcs[i - 1][j].length() > lcs[i][j - 1].length()) ? lcs[i - 1][j] : lcs[i][j - 1];
            }
        }
    }
    if (dp[str1.length()][str2.length()] != 0)
        cout << dp[str1.length()][str2.length()] << '\n' << lcs[str1.length()][str2.length()]<<'\n';
    else
        cout << 0;
}