[ BOJ 백준 9252번 - LCS 2 ] 해설 및 코드

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

 

목적

입력으로 주어진 두 문자열의 LCS의 길이와 LCS를 구하자.

 

접근법

1. 다음과 같이 DP로 2차원 배열을 채우자. 문자열 a,b가 있을 때, s[i][j]는 a[0~i], b[0~j]까지의 lcs의 길이이다. 이러한 s[i][j]는 다음 두가지 조건으로 채운다.

• a[i] == b[j] 이면, s[i][j] = s[i-1][j-1] + 1
• 그렇지 않으면, s[i][j] = max(s[i-1][j], s[i][j-1])

 

2. lcs를 구하는 과정은 s[i][j]를 채워나간 방식과 비슷하게 진행한다. 다음 그림의 ?를 s[i][j]라고 한다면 s[i][j]는 A,B,C의 영향을 받게 되며, lcs는 역방향으로 찾아 나간다.

• a[i] == b[j] 이면, A로 이동
• 그렇지 않으면, B와 C중 큰 곳으로 이동

#include<bits/stdc++.h>
#define N 1001
using namespace std;
 
int s[N][N];
char a[N],b[N];
 
void print(int i,int j){
    if(s[i][j]==0)return;
    if(a[i-1]==b[j-1]){
        print(i-1, j-1);
        cout<<a[i-1];
    }else s[i-1][j]>s[i][j-1]?print(i-1,j):print(i,j-1);
}
 
int main(){
    cin>>a>>b;
    int i,j=0;
    for(i=0;a[i];++i)for(j=0;b[j];++j){
        if(a[i]==b[j])s[i+1][j+1]=s[i][j]+1;
        else s[i+1][j+1]=max(s[i][j+1],s[i+1][j]);
        
    }
    cout<<s[i][j]<<'\n';
    print(i,j);
    return 0;
}
 

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.