[BOJ] 9252 LCS2 C++

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

9252번: LCS 2

dp의 대표문제인 LCS문제를 풀었다.

dp의 핵심은 dp배열이 무엇을 의미하는지 알아내는 것이 핵심이다.

i=첫번째 문자열(s1)의 인덱스, j=두번째 문자열(s2)의 인덱스라고 할 때, dp[i][j]는 s1의 i번째 s2의 j번째까지 비교했을 때 LCS2의 최대 크기를 의미하게 된다. LCS를 구하는 알고리즘은 다음과 같다.

1. s1[i]==s2[j]라면 dp[i][j]=dp[i-1][j-1]+1

2. s1[i]!=s2[j]라면 dp[i][j]=max(dp[i-1][j],dp[i][j-1])

아, 그리고 이 문제 같은 경우에는 알파벳 대문자로만 이루어져 있기 때문에 각각의 문자열 첫번째에 '0'을 넣어주면 반복문에서 범위 때문에 넣어야 하는 조건을 빼줄 수 있다.

 

주어진 예제 ACAYKP CAPCAK로 dp[i][j]를 모두 나타내면 다음과 같다.

따라서 dp[s1.size()-1][s2.size()-1]을 출력해주면 된다.

 

이 문제에서는 LCS를 출력해 줘야 하기 때문에 dp를 역추적해야 한다.

빨간색 동그라미가 있는 경우를 출력해주면 되는데 조건은 다음과 같다.

1.s1[i]==s2[j]일 경우 문자를 저장해주고 s1의 i-1번째로 s2의 j-1번째로 간다.

2.s1[i]!=s2[j]일 경우 dp[i][j]==dp[i-1][j]라면 s1의 i-1번째로 s2의 j번째로 그렇지 않을 경우 s1의 i번째로 s2의 j-1번째로 가면 된다.

위 코드는 재귀로 쉽게 구현할 수 있다.

 

코드

#include <iostream>

#include <string>

using namespace std;

int dp[1002][1002];

char memo[1002];

string s1,s2;

 

//역추적 코드

void findlcs(int cnt,int i,int j){

    if(cnt==0) return;

    if(s1[i]==s2[j]){

        //문자열을 찾으면 저장해준다.

        memo[cnt]=s1[i];

        findlcs(cnt-1,i-1,j-1);

    }else{

        if(dp[i][j]==dp[i-1][j]) findlcs(cnt,i-1,j);

        else findlcs(cnt,i,j-1);

    }

}

 

int main(){

    cin>>s1>>s2;

    s1='0'+s1;

    s2='0'+s2;

    //LCS의 크기를 구해주는 알고리즘

    for(int i=0;i<s1.size();i++){

        for(int j=0;j<s2.size();j++){

            if(i==0||j==0){

                dp[i][j]=0;

                continue;

            }

            if(s1[i]==s2[j]){

                dp[i][j]=dp[i-1][j-1]+1;

            }else{

                dp[i][j]=max(dp[i][j-1],dp[i-1][j]);

            }

        }

    }

    

    int len=dp[s1.size()-1][s2.size()-1];

    cout<<len<<'\n';

    if(len==0) return 0;

    int cnt=len;

    findlcs(len,s1.size()-1,s2.size()-1);

    for(int i=1;i<=cnt;i++) cout<<memo[i];

    return 0;

}