[BOJ] 팰린드롬 분할

팰린드롬 분할

TimeLimit	MemoryLimit	Condition	TAG
2s	128MB	(1 ≤ N ≤ 2500)	Dynamic Programming

코드 처음할 때 3차원으로 정의해놓고.. 쓰다보니까 그냥 아니라서 혼자 생각해서 풀었는데요

dp[i][j]는 i - j + 1부터 i까지 점프를 뛸 때(즉 팰린드롬일 때) 최소 값을 저장하고 이후에 돌면서 최솟값 업데이트해주고 그걸로 시간초과 피하면서 처리하면 AC!

정답 코드

#include <iostream>
#define inf 2100000000

using namespace std;
using ll = long long;

int dp[2501][2501]; // [i][j][k] i번째 수일 때 i - j까지의 연속된 순서가 팰린드롬일 때 현재 나눠진 팰린드롬의 개수
int visited[2501];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    string input;
    
    cin >> input;
    int result = (int) input.size();
    
    int n = result;
    // 먼저 자기 자신 일단 넣어두고, 다음으로
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) dp[i][j] = inf;
    }
    
    for(int i = 0; i <= n; i++) dp[0][i] = 0;
    dp[1][1] = 1;
    
    visited[0] = 0;
    visited[1] = 1;
    
    for(int i = 2; i <= n; i++){
        dp[i][1] = min(dp[i-1][1] + 1, dp[i-1][2]);
        visited[i] = inf;
        
        
    }
//        dp[i][
        
////    }
//    
//    
    for(int i = 2; i <= n; i++){
        
        for(int k = 1; k <= i; k++) {
            dp[i][1] = min(dp[i][1], dp[i-1][k] + 1);
            visited[i] = min(visited[i], dp[i][1]);
        }
        
        
        for(int j = 1; j < i; j++){
            
            
            
            if(input[j - 1] != input[i - 1]) continue;

//            else {
//                if(input[i-j-1] == 'R'){
//                    cout <<i << " "<< j << "\n";
//                }
//            }
            if(dp[i - 1][i - j - 1] >= inf) continue;
            
//            cout << "check: " << input[i-j-1] << " " << input[i] << "\n";
//            cout << "dp: " << dp[i-1][j-1] << "\n";
//
            dp[i][i - j + 1] = min(dp[i][i - j + 1], visited[j-1]+1);
            visited[i] = min(dp[i][i-j+1], visited[i]);
            
        }
    }
    
//    
//    for(int i = 1; i <= n; i++){
//        for(int j = 1; j <= n; j++){
//            if(dp[j][i] == inf) cout << "O ";
//            else cout << dp[j][i] << " ";
//        }
//        cout << "\n";
//    }
    
    cout << visited[n];
    
    
}
// ABACAAB
// QWERTYTREWQWERT


// DCADD
// 16
// BBCDDECAECBDABADDCEBACCCBDCAABDBADD
// BBCDDECAECBDABADDCEBACCCBDCAABDBADD