1509 펠린드롬 분할

수정 전> 시간초과

#include <stdio.h>
#include <iostream>
#include <string>
 
using namespace std;
 
string str;
int dp[2505][2505] = { 0 };
 
int main() {
    getline(cin, str);
    
    str = "0" + str;
    int len = str.length() - 1;
 
    for (int i = 1; i <= len; i++) {
        dp[i][i] = 1;
    }
 
    for (int i = 1; i <= len; i++) {
        for (int j = i+1; j <= len; j++) {
            if (str[i] == str[j]) {
                int d;
                for (d = 0; i + d < j - d; d++) {
                    if (str[i + d] != str[j - d]) {
                        break;
                    }
                }
                if (i + d >= j - d) {
                    dp[i][j] = 1;
                }
            }
        }
    }
 
    for (int d = 1; d < len;d++) {
        for (int i = 1; i + d <= len;i++) {
            if (dp[i][i + d] != 1) {
                int minV = 30000;
                for (int mid = i; mid + 1 <= i + d; mid++) {
                    if (minV > dp[i][mid] + dp[mid + 1][i+d]) {
                        minV = dp[i][mid] + dp[mid + 1][i+d];
                    }
                }
                dp[i][i+d] = minV;
            }
        }
    }
 
    printf("%d", dp[1][len]);
}

수정 후> 시간 내 AC

#include <stdio.h>
#include <string>
#include <iostream>
 
using namespace std;
 
int dp[3000] = { 0 };
string arr;
 
int main() {
    cin >> arr;
    arr = "0" + arr;
    int len = arr.length() - 1;
 
    for (int i = 1; i <= len; i++) {
        int minV = 300000;
        for (int mid = 0; mid < i; mid++) {
            int d;
            for (d = 0; mid + 1 + d < i - d; d++) {
                if (arr[mid + 1 + d] != arr[i - d]) {
                    break;
                }
            }
            if (mid + 1 + d >= i - d) {
                int val = dp[mid] + 1;
 
                if (minV > val) {
                    minV = val;
                }
            }
            dp[i] = minV;
        }
    }
    printf("%d", dp[len]);
}