문제

세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.

분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열이 주어진다. 이 문자열은 알파벳 대문자로만 이루어져 있고, 최대 길이는 2,500이다.

출력

첫째 줄에 팰린드롬 분할의 개수의 최솟값을 출력한다.

예제 입력 1

BBCDDECAECBDABADDCEBACCCBDCAABDBADD

예제 출력 1

22

예제 입력 2

AAAA

예제 출력 2

1

예제 입력 3

ABCDEFGH

예제 출력 3

8

예제 입력 4

QWERTYTREWQWERT

예제 출력 4

5

나의 풀이

import sys
input = sys.stdin.readline

str_list = input().rstrip()
L = len(str_list)
dp = [2500 for _ in range(L+1)] #2500 = 문자열의 최대 길이 = 가능한 팰린드롬 분할의 최대 길이
dp[-1] = 0
is_p = [[0 for j in range(L)] for i in range(L)] #is_p[i][j]는 i부터 j가 팰린드롬이라면 1, 아니면 0을 반환

for i in range(L): #길이 1짜리 팰린드롬
    is_p[i][i] = 1

for i in range(1,L): #길이 2짜리 팰린드롬
    if str_list[i-1] == str_list[i]:
        is_p[i-1][i] = 1

for k in range(3, L + 1): #길이 3이상 팰린드롬
    for start in range(L - k + 1):
        end = start + k - 1
        if str_list[start] == str_list[end] and is_p[start + 1][end - 1]:
            is_p[start][end] = 1
            #---------------------------------여기서부터 이해가 어려웠음
for end in range(L):
    for start in range(end + 1):
        if is_p[start][end]:
            dp[end] = min(dp[end], dp[start - 1] + 1)
        else:
            dp[end] = min(dp[end], dp[end - 1] + 1)

print(dp[L - 1])

나의 풀이

앞선 문제에서 만들었던 팰린드롬 점화식을 그대로 재활용했다.
하지만 문제에선 팰린드롬 여부가 아닌 팰린드롬으로 쪼개지는 분할 개수의 최솟값을 물어보고 있기 때문에 dp에서는 해당 index 까지의 분할 개수의 최솟값을 담아야 하므로,
is_p라는 2차원 리스트를 하나 더 만들어서 여기에 팰린드롬 여부를 기록했다.