[DP] 9252번 LCS2

9252번 LCS 2

 

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

 

문제

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

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

 

입력

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

 

출력

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

LCS가 여러 가지인 경우에는 아무거나 출력한다.

 

예제 입력

ACAYKP
CAPCAK

 

예제 출력

4
ACAK

 

해결방법

LCS(Longest Common Subsequence) 를 적용한 DP 문제이다

 

 

⭐️ 솔루션 ⭐️

LCS 문제 에서 LCS 를 출력하라는 조건이 추가된 문제이다

이를 위해 2차원 배열을 역추적하여 LCS 를 구하는 솔루션을 사용하였다

 

0  0  0  0  0  0  0
0  0  1  1  1  1  1
0  1  1  1  2  2  2
0  1  2  2  2  3  3
0  1  2  2  2  3  3
0  1  2  2  2  3  4
0  1  2  3  3  3  4

행 : ACAYKP

열 : CAPCAK

 

맨 아래의 오른쪽 노드에서 부터 역추적을 시작한다

1. d[i][j] = d[i-1][j]
2. d[i][j] = d[i][j-1]
3. d[i][j] != d[i][j-1] && d[i][j] != d[i-1][j]

 

위와 같이 3가지 경우가 존재하는데

1번째 경우라면 i-1 , 2번째 경우라면 j-1 , 3번째 경우라면 i-1, j-1 수행 후, 해당 문자를 답에 넣어준다

 

 

 

소스코드

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

string s1,s2;
vector<char> ans;
int l1,l2;
int d[1001][1001];

void dp(){
    for(int i=1; i<=l1; i++){
        for(int j=1; j<=l2; j++){
            if(s1[i-1] == s2[j-1]){
                d[i][j] = d[i-1][j-1] + 1;
            }else{
                d[i][j] = max(d[i-1][j],d[i][j-1]);
            }
        }
    }
    
    // LCS 길이 출력
    cout << d[l1][l2] << "\n";
    
    // 2차원 배열을 역추적하여 LCS 저장
    int i = l1;
    int j = l2;
    while(i!=0 && j!=0){
        if(d[i][j] == d[i-1][j]){
            i--;
        }else if(d[i][j] == d[i][j-1]){
            j--;
        }else{
            ans.push_back(s1[i-1]);
            i--;
            j--;
        }
    }
    
    for(int i=(int)ans.size()-1; i>=0; i--){
        cout << ans[i];
    }
    cout << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> s1 >> s2;
    
    l1 = (int) s1.size();
    l2 = (int) s2.size();
    
    dp();
    
    return 0;
}