BOJ 9252

LCS 2 성공 스페셜 저지

 

0.1 초 (하단 참고)

256 MB

26357

9345

7222

38.384%

문제

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

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

입력

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

출력

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

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

예제 입력 1 복사

ACAYKP
CAPCAK

예제 출력 1 복사

4
ACAK

내가 제일 못하는 알고리즘 짜놓고 경로찍는 문제이다.

 

LCS는 넘어가고, 경로를 찍는 방법은 이 문제의 예제를 예시로 들었을떄

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

이런 배열이 생기게 된다.

 

여기서 [N][M]번째 원소부터 시작하여 역방향으로 봐주면 되는데,

중요한 점은 뒤에서 가므로 [N][M]번째 원소에 해당하는 s1[N], s2[M]이 같다면 여기서 LCS가 무조건 하나 증가한 것인것을 아는거다. 

그러므로 이런 경우에는 N, M을 각각 -1해주고 그렇지 않은 경우에는 s1[N], s2[M]이 같은 경우를 찾아야 하기 때문에

[N-1][M] 또는 [N][M-1]을 계산해 다음 인덱스로 만들어주는 것이다.

다만 두개 다 할필요는 없고, 어처피 위로가든 옆으로가든 무조건 같은 원소가 생기기 때문에 그냥 조건문으로 해주면 된다.

 

#include <iostream>
#include <string>
using namespace std;
string s1, s2, ans;
int arr[1001][1001], arr2[1001];
int main(){
    cin>>s1>>s2;
    for(int i=1; i<=s1.size(); i++)
        for(int j=1; j<=s2.size(); j++){
            if(s1[i-1] == s2[j-1])
                arr[i][j] = arr[i-1][j-1]+1;
            else 
                arr[i][j] = max(arr[i-1][j], arr[i][j-1]);
        }
    int x = s1.size(), y=s2.size();
    while(x != 0 && y != 0){
        if(s1[x-1] == s2[y-1]){
            ans.push_back(s1[x-1]);
            x -= 1;
            y -= 1;
            continue;
        }
        if(arr[x][y] == arr[x-1][y])
            x -= 1;
        else if(arr[x][y] == arr[x][y-1])
            y -= 1;
    }
    cout<<arr[s1.size()][s2.size()]<<'\n';
    while(!ans.empty()){
        cout<<ans.back();
        ans.pop_back();
    }
}