백준 1701번 Cubeditor - C++(cpp) 풀이

---

 

1. dp(a, b): 가장 길게 일치하는 부분 문자열 S[a...], S[b...]의 길이
2. S[a] == S[b] 인 경우 dp(a, b) = 1 + dp(a+1, b+1)
3. S[a] != S[b]인 경우 dp(a, b) = 0

 

1. dp(a, b): 가장 길게 일치하는 부분 문자열 S[a...], S[b...]의 길이

 2번 이상만 등장하면 되므로, 서로 다른 시작점 2개가 있으면 된다. 따라서 dp(a, b)를 위와 같이 정의하자.

 

2. S[a] == S[b] 인 경우 dp(a, b) = 1 + dp(a+1, b+1)

 S[a] == S[b]인 경우, 첫 글자가 일치하므로 1+ dp(a+1, b+1)이 된다.

 

3. S[a] != S[b]인 경우 dp(a, b) = 0

 첫 글자부터 일치하지 않는 경우에는 0이다.

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

const int MAX = 5000;

string S;
int cache[MAX][MAX];

// dp(a, b): 가장 길게 일치하는 부분문자열 S[a...]와 S[b...]의 길이
int dp(int a, int b) {
    if (b == S.size() || a == b) return 0;
    
    int& ret = cache[a][b];
    if (ret != -1) return ret;
    
    if (S[a] != S[b]) ret = 0;
    else ret = 1 + dp(a+1, b+1);
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    memset(cache, -1, sizeof(cache));
    
    cin >> S;
    
    int max_len = 0;
    for (int i=0; i<S.size()-1; i++) {
        for (int j=i+1; j<S.size(); j++) {
            max_len = max(max_len, dp(i, j));
        }
    }
    
    cout << max_len;

    return 0;
}