[BOJ 5582] 공통 부분 문자열

간단한 문제인데 벙쪄있었다. 왜 그랬을까?

 

 

 

 

아마도 dp를 공통 부분 문자열의 최장 길이로 정의할려다가 보니 점화식을 못세워서 뇌정지가 왔던 거 같다..

 

 

 

 

이 문제를 풀기 위해서는, 점화식을 세워야 한다.

 

 

 

 

S1과 S2의 각 각 인덱스를 i와 j라고 하자. dp는 S1[i]와 S2[j]가 공통 부분 문자열의 마지막 부분일 때, 공통 부분 문자열의 길이의 값이다.

 

 

 

 

dp[i][j] = dp[i - 1][j - 1] + 1 (S1[i] == S2[j])

dp[i][j] = 0 (S1[i] != S2[j])

 

 

 

 

위의 점화식을 통해서 코드를 작성하면 된다.

 

 

 

 

 

해설코드(C++).

 

#include <iostream>
#include <cstring>
 
using namespace std;
 
string s1, s2;
int dp[4001][4001] = { 0 };
int result = 0;
 
int main() {
    cin >> s1 >> s2;
    for(int i = 1; i <= s1.length(); i++){
        for(int j = 1; j <= s2.length(); j++){
            dp[i][j] = 0;
            if(s1[i - 1] == s2[j - 1]){
                dp[i][j] = 1 + dp[i - 1][j - 1];
                result = max(result, dp[i][j]);
            }
        }
    }
 
    cout << result << endl;
    return 0;
}