[백준 1509번] 파이썬 - 팰린드롬 분할

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

1509번: 팰린드롬 분할

 

# 조건

• 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다.
• 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.
• 분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오.

 

입력

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

 

출력

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

 

# 접근 방법

• 회문의 시간을 확연하게 줄여주는 manacher algorithm을 이용해준다.
• 범위를 N*2-1로 해주어 홀수, 짝수 일 때를 번갈ㄹ아 가며 팰린드롬 여부를 확인해준다.

from sys import stdin
input = stdin.readline


def solve():
    Str = input()[:-1]
    N = len(Str)
    ans = [2500] * (N + 1)
    ans[0], ans[N] = 1, 0

    # 2*N-1 인 이유: 홀수길이, 짝수길이 번갈아가며 팰린드롬 여부 확인하기 위해
    for i in range(1, 2 * N - 1):
        # i가 홀수: 짝수길이, i가 짝수: 홀수길이
        start, end = i // 2, (i + 1) // 2
        while 0 <= start and end < N:
            if Str[start] == Str[end]:
                if ans[start-1] + 1 < ans[end]:
                    ans[end] = ans[start-1] + 1
                start -= 1
                end += 1
            else: break

    return ans[N-1]


print(solve())