1. 2차원 bool 형 배열 palindrome에 모든 팰린드롬을 저장.
-> palindrome[i][j] 엔 시작이 i이고 끝이 j인 문자열이 팰린드롬인지 아닌지 저장돼있음
-> 구하는 법은 처음부터 i = 0~length, j = i~length; 로 가면서 팰린드롬인지 확인하고,
팰린드롬이면 Manacher’s Algorithm 으로 그 사이 팰린드롬을 전부 표시
아니면 그냥 넘어간다
-> 팰린드롬일경우 그 사이는 전부 표시했으니, 이중for문 진행하면서 palindrome[i][j]이 true면 그냥 넘어가면 된다.
2. 저장한 palindrome을 바탕으로 바텀업 DP 시행
-> DP[length] : 각 시작점이 x일때 이후 최소의 분할수를 기록한 것.
-> DP함수 처음 호출할 때 시작을 0으로 하고, 끝점을 0에서 length까지 검사하며 각 끝점에 대해 팰린드롬이면 start + 1를 주며 아래로 내려간다.
-> 그리고 start가 length와 같아지면 0을 반환하며 1씩 증가하며 올라간다.
-> 이때 각 시작점에선 모든 끝점에 대해 반환값이 최소인 것을 result에 기록하고, 모든 끝점에 대한 검사가 끝나면 DP[start]에 result를 기록하고 반환한다.
바텀업으로 재귀 DP 사용하니 느림
다른방법
-> 해보니 시간은 비슷하다. 그냥 다른 DP 방식도 있는걸로 알고 넘어가자
1. 반복문으로, i : 1~length / j : i+1~length 를 검사
2. 이전에 저장된 값이 있으면, DP[i-1] + 1하고 비교했을 때 더 크면 그걸로 업데이트 아니면 그냥 넘어가기
3. 저장된값이 없으면 DP[i-1] + 1 저장
4. 각 시작부분은 시작 시 위 2~3을 한다.
#include <iostream>#include <string>#define MAX_LENGTH 2500using namespace std;//2차원 배열로 모든 팰린드롬 저장//첫번째 줄에 팰린드롬인것을 하나씩 넣음//그리고 오른쪽 아래로 내려가며 가능한 것을 최대한 넣자.//ex) map[0][0] 은 무조건 팰린드롬이니 고름 -> map[1][1]에서 가장가까운 팰린드롬 고름 map[1][1] -> map[2][2] -> ..... 총길이 2500, -> map[1][2] ...map[1][3].. 이렇게 진행?//위처럼 진행할 경우 2500*2500 + 2499*2499 + ... 총 26억 계산 -> 시간초과//가장가까운이 아닌, 가장 먼곳부터 골라보자. map[0][n] ... 그리고 길이가 이미고른 길이보다 길면 중간종료 하는 식으로?//하지만 최악의 경우 또 26억이 됨//DP = 위 계산을 바텀업방식으로 하여 DP[x] 에 길이를 저장하는 방식으로 해보자int length, DP[MAX_LENGTH];char input[MAX_LENGTH];bool palindrome[MAX_LENGTH][MAX_LENGTH];void makePalindrome();bool isPalindrome(int start, int end);void recordPalindrome(int start, int end);int getMinSplit(int start);int min(int a, int b) { return a < b ? a : b;}int main() { string tempInput; cin >> tempInput; length = tempInput.size(); for (int i = 0; i < tempInput.size(); i++) input[i] = tempInput[i]; makePalindrome(); cout << getMinSplit(0);}void makePalindrome() { for (int i = 0; i < length; i++) { for (int j = length - 1; j >= i; j--) { if (palindrome[i][j] != 0) continue; if (isPalindrome(i, j)) recordPalindrome(i, j); else palindrome[i][j] = 0; } }}bool isPalindrome(int start, int end) { for (; start < end; start++, end--) if (input[start] != input[end]) return false; return true;}void recordPalindrome(int start, int end) { for (; start <= end; start++, end--) palindrome[start][end] = 1;}int getMinSplit(int start) { if (start == length) return 0; if (DP[start]) return DP[start]; int result = 200000000; for (int i = length-1; i >= start; i--) if (palindrome[start][i]) result = min(result, getMinSplit(i + 1) + 1); return DP[start] = result;}