Boj 9251 c++ LCS

유명한 최장부분 공통수열 문제. 아이디어를 떠올리지 못해 구글링을 하였다.

 

이때, dp배열의 정의는 i, j번째 문자열 원소까지 비교하였을 때 LCS의 길이이다.

 

s1[0]과 s2[0]을 비교한 값은 dp[1][1]에 들어가므로 인덱스 보정에 유의해야 한다.

 

그림을 그려보면 이해가 쉽다. 같은 문자가 나오면 바로 이전까지의 공통부분+1을 해주고, 두 문자를 비교했을 때 다르면 두 대각선 사이 중 큰 것을 출력해주면 된다. 

 

풀어서 설명해보겠다.

 

우선 경우는 크게 두가지로 나눌 수 있다.

1. i번째 인덱스의 문자와 j번째 인덱스의 문자가 같을 때:
이때는 공통부분이 생겼기에 아무런 문제 없이 배열을 업데이트 하면된다.

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

 

2.  i번째 인덱스의 문자와 j번째 인덱스의 문자가 같지 않을 때:

이 경우에는 세가지 경우가 존재한다.

 

2-1. i번째 인덱스와 j-1번째 인덱스를 비교한 값이 더 클때

 

2-2. i-1번째 인덱스와 j번재 인덱스를 비교한 값이 더 클때

 

2-3. 위의 두 결과값이 같을 때(i~i-1, j~j-1 에 LCS 해당사항 없음)

 

이때 2-3은 경계상황이기에 둘중 하나에 포함시켜줄 수 있다.

현재는 최대 길이를 구하는 것이기에 2-1, 2-2, 2-3 중 최댓값만을 취하면 되는 것이다.

 

 

코드는 다음과 같다.

#include<iostream>
using namespace std;
int dp[1001][1001];
int main(){
    string s1, s2;
    cin>>s1>>s2;
    int n=s1.length(), m=s2.length();
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(s1[i]==s2[j]){
                dp[i+1][j+1]=dp[i][j]+1;
            } else {
                dp[i+1][j+1]=max(dp[i][j+1], dp[i+1][j]);
            }
        }
    } cout<<dp[n][m];
}