# [Gold I] 팰린드롬 분할 [문제 링크](https://www.acmicpc.net/problem/1509) ## 문제 설명 <p>세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.</p> <p>분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 문자열이 주어진다. 이 문자열은 알파벳 대문자로만 이루어져 있고, 최대 길이는 2,500이다.</p> ## 출력 <p>첫째 줄에 팰린드롬 분할의 개수의 최솟값을 출력한다.</p> ## 풀이 #### dp[i]를 i번째 문자까지의 최소 팰린드롬 수로 두고 풀었다. 팰린드롬인지 확인하는 2차원 dp를 만들어 푸는 것이 정해인 것 같지만, 안 만들어도 시간 안에 풀린다. ``` c++ #include<bits/stdc++.h> using namespace std; string s; int dp[2500]; // dp[i] : i번째 문자까지의 최소 팰린드롬 수 bool isPalindrome(int left, int right) { int len = right-left+1; for(int i=0;i<len/2;i++) { if(s[left+i]!=s[right-i]) return false; } return true; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> s; // 0-i 범위가 팰린드롬인 경우 i는 1개의 팰린드롬으로 분할 가능 for(int i=0;i<s.length();i++) dp[i]=i+1; for(int i=1;i<s.length();i++) { if(isPalindrome(0, i)) { dp[i]=1; } } // i+1부터 j까지 팰린드롬인지 확인하며 팰린드롬이면 분할 for(int i=0;i<s.length()-1;i++) { for(int j=i+1;j<s.length();j++) { if(isPalindrome(i+1, j)) { dp[j] = min(dp[j], dp[i]+1); } } } cout << dp[s.length()-1]; } ```