백준 1509

[백준/c++] 1509번 - 팰린드롬 분할

문제 https://www.acmicpc.net/problem/1509 문제세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오. 입력첫째 줄에 문자열이 주어진다. 이 문자열의 최대길이는 2,500이다. 출력첫째 줄에 팰린드롬 분할의 개수의 최솟값을 출력한다. 풀이과정 1.규칙dp이므로 점화식과 메모이제이션을 이용합니다.문자열을 분할할 수 있는 최솟값을 출력합니다. 2.순서 팰린드롬?(https://it-and-life.tistory.com/137)에서 약간 변형된 문제로, 문자열..