✅ DP

문제

1. 해결 로직

문자열의 최대길이가 각 4000이므로 그때 그때 같은 부분이 있는지 판별할 수 없다.

따라서 DP를 사용해 각 공통 문자 자리까지의 최대 길이를 저장해가며 판별한다.
dp[i][j] = i부분과 j부분의 문자가 같다면 그 이전의 최대길이 + 1

2. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

string s, t;
int ans, dp[4001][4001];
int main(){
    cin >> s >> t;
    for(int i = 0; i < s.size(); i++){
        for(int j = 0; j < t.size(); j++){
            if(s[i] == t[j]){
                dp[i+1][j+1] = dp[i][j] + 1;
                ans = max(ans,dp[i+1][j+1]);
            }
        }
    }
    cout << ans << '\n';
}

3. 시간 복잡도

4. Review

dp를 떠올리는게 중요했던 문제

5. Reference

https://codecollector.tistory.com/1070