[BAEKJOON] 1509 팰린드롬 분할

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <string> using namespace std; int main() { vector<vector<int>>isPaline(2501, vector<int>(2501, 0)); vector<long long>DP(2501, 0); string input; cin >> input; int input_size = input.size(), start, end; for (int x = 0; x < input_size; x++) isPaline[x][x] = 1; for (int x = 0; x < input_size; x++) { start = x; end = x + 1; while (start > -1 && end < input_size) { if (input[start] != input[end]) break; else isPaline[start][end] = 1; start--; end++; } start = x - 1; end = x + 1; while (start > -1 && end < input_size) { if (input[start] != input[end]) break; else isPaline[start][end] = 1; start--; end++; } } for (int start = 0; start < input_size; start++) { for (int end = 0; end < input_size; end++) { if (isPaline[start][end]) { if (DP[end + 1] == 0 || (DP[end + 1] != 0 && DP[end + 1] > DP[start] + 1)) DP[end + 1] = DP[start] + 1; } } } printf("%lld", DP[input_size]); return 0; }

1) 팰린드롬의 여부를 판단하는 isPaline

팰린드롬인 경우

1. 자기자신

2. BAAB (짝수)

3. BACAB (홀수)

2) 경우의 수를 저장하는 DP

0으로 초기화

DP[분할한 마지막] = DP[분할한 시작-1]+1

DP[분할한 마지막] == 0 이면 초기화한 수 즉 DP[분할한 마지막] = 1