[백준,c++] 5582번 - 공통 부분 문자열

문제

5582번: 공통 부분 문자열

 

풀이

// 23:14~23:57

#include <iostream>
using namespace std;

int dp[4001][4001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    string s1,s2; cin>>s1>>s2;
    int ans = 0;
    
    for(int i=0; i<s1.length(); i++){
        for(int k=0; k<s2.length(); k++){
            if(i==0||k==0){
                if(s1[i]==s2[k]) dp[i][k]=1;
            }
            else if(s1[i]==s2[k]) dp[i][k] = dp[i-1][k-1]+1;
            ans = max(ans, dp[i][k]);
        }
    }
    cout<<ans;
    
}

 

풀이

DP문제였습니다. 

위 이미지와 같이 문자가 같다면 좌측 상단 대각선 값에서 +1 해주는 식으로 전부 탐색한 후, 가장 큰 값을 출력하면 연속하는 가장 큰 길이가 됩니다.