[Python] 백준 1509 팰린드롬 분할

 

 

문제

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

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

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

 

 

 

 

 

 

난이도

골드 1

 

 

 

 

 

 

 

 

코드

import sys

def palin() :
    for i in range(n) :
        isPal[i][i] = True

    for i in range(2,n) :
        ii = i
        for j in range(1,n+1-i) :
            if x[ii] == x[j] :
                if ii - j <= 2 :
                    isPal[j][ii] = True 
                else :
                    if isPal[j+1][ii-1] :
                        isPal[j][ii] = True

            ii += 1

x = [0] + list(sys.stdin.readline().rstrip())
n = len(x)
isPal = [[False] * n for _ in range(n)]
palin()

dp = [float('inf')] * n
dp[0] = 0

for i in range(1,n) :
    for j in range(i+1) :
        if x[i] == x[j] :
            if isPal[j][i] :
                dp[i] = min(dp[j-1]+1,dp[i])

print(dp[n-1])

 

 

 

 

 

 

 

 

풀이과정

1. 팰린드롬 판단

이차원 배열(isPal)을 만들어서 전체적으로 j번째 문자부터 i번째 문자까지가 펠린드롬인지 확인하게 하였다.

일단 두 문자가 같지않으면 무조건 펠린드롬이 아니기 때문에 같은경우에서,

j랑 i의 차이가 2보다 같거나 작으면 무조건 펠린드롬이다.

그렇지 않은 경우에서는 그 사이가 펠린드롬이면 펠린드롬이다. 이차원 배열을 계단식으로 채워가기 때문에 그 사이가 펠린드롬인지는 미리 구해져있을것이다.

 

 

2. DP

DP를 이용해서 처음부터 i까지의 최소분할갯수를 저장해두었다. 

i를 돌아가며 그 전에 나왔던 부분과 펠린드롬이 되는 부분이 있으면 j 이전까지의 최소 분할 개수에 1을 더한 값으로 dp값을 갱신하였다.