[백준] 팰린드롬 분할

https://www.acmicpc.net/problem/1509

1509번: 팰린드롬 분할

DP를 활용하여 해결하였습니다. 현재 문자가 추가되었을 때 얻을 수 있는 최소 팰린드롬 분할의 개수를 그때 그때 구해주면 됩니다. dp[i]는 i번째 문자까지 얻을 수 있는 최소 분할 개수라고 가정했을 때 ABAC로 예를 들어보겠습니다. 최초에는 A가 추가됩니다. 문자 하나는 펠린드롬이고 dp[i] = 1입니다. B를 추가해봅니다. AB는 팰린드롬이 아니므로 dp[2] = 2가 됩니다. A + BA(dp[1]  + 2), AB + A(dp[2] + 1),  ABA(dp[0] + 1) 중 최소값을 택하면 됩니다. ABA의 경우 1 ~ 3번째 문자를 보았을 때 팰린드롬이므로 분할이 1개가 되고 dp[0] = 0이므로 dp[3] = 1이 됩니다. ABAC도 마찬가지입니다. dp[1] + 3, dp[2] + 2, dp[3] + 1, dp[0] + 4중 최소값을 고르므로 2가 됩니다. 

 

isPelin의 역할은 i ~ j까지의 문자열이 팰린드롬인지를 저장하고 있습니다. 추가하고자하는 문자열을 추가했을때 이전 문자열들과 비교하여 팰린드롬인지 여부를 저장하고 있습니다.

import sys
from collections import deque
sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

INT_MAX = sys.maxsize

pelin = ['X'] + list(input().rstrip())

n = len(pelin)
dp = [INT_MAX] * (n + 1)

dp[0] = 0
dp[1] = 1

# pelin[i][j]: i ~ j가 팰린드롬인지를 체크한다.
isPelin = [
    [False] * n
    for _ in range(n)
]

for i in range(n):
    isPelin[i][i] = True

for i in range(2, len(pelin)):
    dp[i] = dp[i - 1] + 1

    for j in range(1, i):

        # i ~ j가 팰린드롬인지를 확인
        if pelin[i] == pelin[j]:
            # 길이가 2인 문자열 판별
            if i - j == 1:
                isPelin[i][j] = 1
                isPelin[j][i] = 1
            elif isPelin[j + 1][i - 1]:
                isPelin[i][j] = 1
                isPelin[j][i] = 1

        # 현재 i ~ j가 팰린드롬인 경우
        if isPelin[i][j]:
            dp[i] = min(dp[i], dp[j - 1] + 1)
        # 현재 구간이 아니면 각각 나눠서 구해야한다.
        else:
            dp[i] = min(dp[i], dp[j - 1] + (i - j + 1))

print(dp[n - 1])