[LCS] 백준 9252 :: LCS 2

LCS 2 성공스페셜 저지

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	8372	3392	2588	41.897%

문제

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

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

입력

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

출력

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

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

예제 입력 1 

ACAYKP
CAPCAK

예제 출력 1 

4
ACAK

     

 문제 풀이

1차 풀이 (  5904 KB,  4 ms)

Bottom-UP 방식의 LCS 알고리즘 사용.

LCS 알고리즘으로 만들어진 테이블을 가지고.

끝에서부터 시작하여 역추적하며 실제 원소를 알아낸다.

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

const int SIZE = 1000;

int cache[SIZE+1][SIZE+1];
char A[SIZE+1];
char B[SIZE+1];

int main()
{
        cin.tie(nullptr);
        ios::sync_with_stdio(false);


        memset(cache, 0, sizeof cache);
        cin >> (A+1);
        cin >> (B+1);

        for(auto i=1; i<=strlen(A+1); i++){
                for(auto j=1; j<=strlen(B+1); j++){
                        if(A[i]==B[j]) cache[i][j] = cache[i-1][j-1]+1;
                        else cache[i][j] = max(cache[i-1][j], cache[i][j-1]);
                }
        }


        //! get LCS length.
        cout << cache[strlen(A+1)][strlen(B+1)] << '\n';


        //! get LCS elements.
        stack<char> elem;
        int i = strlen(A+1);
        int j = strlen(B+1);
        while(true){
                if(i==0 || j==0) break;
                if(cache[i][j] == cache[i-1][j]) {
                        i--;
                }
                else if(cache[i][j] == cache[i][j-1]){
                        j--;
                }
                else {
                        elem.push(A[i]);
                        i--;
                        j--;
                }
        }
        while(!elem.empty()){
                cout << elem.top();
                elem.pop();
        }
}