[백준] 1509번 : 펠린드롬 분할

1509번: 팰린드롬 분할

1509번: 팰린드롬 분할

🤔 문제분석

팰린드롬의 분할개수의 최소값을 구하는 문제로, 지정된 start와 end에서 팰린드롬인지 아닌지 판별을 우선 해야한다.

아래의 예로 ABBAAB의 최소 팰린드롬의 개수를 구하는 과정을 보면 이전에 구했던 A, AB, ABB, ABBA … 가 최소개수를 가지고 있어야한다. X라고 표기된건 현재 팰린드롬이 아니라 무시한다.

💻 코드

import sys
input = sys.stdin.readline

word = str(input().strip())
L = len(word)

is_p = [[False for _ in range(L)] for _ in range(L)]
dp = [0 for _ in range(L+1)]

for i in range(L):
    is_p[i][i] = True

for i in range(L-1):
    if word[i] == word[i+1]:
        is_p[i][i+1] = True

for k in range(2, L):
    for i in range(L-k):
        start = i
        end = i+k
        if word[start] == word[end] and is_p[start+1][end-1]:
            is_p[start][end] = True

for end in range(L):
    dp[end+1] = float('inf')
    for start in range(end + 1):
        if is_p[start][end]:
            dp[end+1] = min(dp[end+1], dp[start] + 1)

print(dp[L])

🎯 피드백 및 개선사항

팰린드롬인지 아닌지에대한 판별은 쉽게 해결 할 수 있었으나, 최소 분할 팰린드롬의 개수를 구하는과정은 문제를 풀면서 생각을 많이 해보게 되었다. 이전에 구했던 최소팰린드롬의 개수를 하나하나씩 다 비교해보면서 현재 리터리에션에서의 펠린드롬의 최소 개수를 최소화 한다.