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

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

1509번: 팰린드롬 분할

 

문제 해결

• 팰린드롬은 좌우 대칭인 문자열을 의미한다
• 문자를 하나씩 나누면 무조건 팰린드롬 분할이 된다.
• 두 개씩 보면서 팰린드롬을 확인하는 것도 어렵지 않다. $O(N)$
• 3개 이상일 때는 어떻게 할 수 있을지 어려웠다.
• 길이를 3부터 L까지 늘려나가면서 $l$ 확인한다.
• 시작점을 0부터 $L-l$까지 이동하며 잡고 끝점을 시작점 + $l$ -1로 잡아서 문자열[start] == 문자열[end] 그리고 start+1부터 end-1까지 팰린드롬이면 start에서 end까지 팰린드롬이다.
• 끝점을 잡고 시작점을 0부터 끝점까지 이동하면서 시작점부터 끝점이 팰린드롬이면 dp[end] = min(dp[end], dp[start-1] + 1)을 계산한다. 만약 팰린드롬이 아니면 dp[end] = min(dp[end], dp[end-1] + 1)
• DP를 활용하는 것이 아직 많이 약한 느낌을 받았다.

 

CODE

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline


def palindrome():
    for i in range(L):
        is_p[i][i] = 1
    
    for i in range(1,L):
        if string[i-1] == string[i]:
            is_p[i-1][i] = 1
    
    for l in range(3, L+1):
        for start in range(L-l+1):
            end = start + l -1
            if string[start] == string[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) # 하나로 묶을 수 있는가 혹은 2개로 쪼개지는가?
            else:
                dp[end] = min(dp[end], dp[end-1] + 1)

if __name__ == "__main__":
    string = input().strip()
    L = len(string)
    dp = [2500 for _ in range(L+1)]
    dp[-1] = 0
    is_p = [[0 for _ in range(L)] for _ in range(L)]
    
    palindrome()
    print(dp[L-1])