[백준/C++] 알고리즘 5582번 공통 부분 문자열

오늘은 백준 알고리즘 5582번 공통 부분 문자열문제를 풀어보는 시간을 가져보겠습니다.

이 문제는 다이나믹프로그래밍으로 접근하면 수월하게 풀 수 있습니다.

​

문제 먼저 보겠습니다.

 

이 문제는 행렬테이블을 그려서 규칙성을 발견하여 점화식을 만들어 풀 수 있습니다

 

위의 그림처럼 문자열 두 개의 문자가 같을 때 이전에 같았던 dp[i-1][j-1] + 1 임을 파악할 수 있고

이를 토대로 arr1[i] == arr2[j]같다면 dp[i][j] = dp[i-1][j-1] +1 임을 이끌어낼 수있습니다.

​

코드는 다음과 같습니다.

#include <iostream>
using namespace std ;
string arr1;
string arr2;
int dp[4001][4001]= {};

int ans;
int max_result = 0 ;
int main() {

    cin>>arr1>>arr2;

    for(int i = 1 ; i < arr1.length()+1 ; i++){
        for(int j = 1 ; j< arr2.length()+1 ; j++){
            if(arr1[i-1] == arr2[j-1]){
                dp[i][j] = dp[i-1][j-1]+1;
                ans = max(ans,dp[i][j]);
             }
            }
        }
        cout<<ans<<endl;
    }