백준 / Python / 1509. 팰린드롬 분할

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

문제 요약

주어진 문자열을 팰린드롬으로 나눌때 나누어진 팰린드롬 갯수의 최솟값을 구하라

 

풀이 요약

1. 각 팰린드롬의 시작점과 끝점을 일단 구해야한다.
2. dp 를 사용하여 특정 idx 에서 팰린드롬을 적용시킨게 나은지, 빼는게 나은지 dp 에 기록한다.
3. 마지막 dp 값을 출력한다.

더 나은 방법으로는 팰린드롬을 구하자마자 dp 를 갱신하는 것이다.

이렇게 하면 겹치는 로직이 생겨서 더 빨리 풀 수 있다.

아래는 팰린드롬 구하기와 dp 갱신을 나눈 로직이다.

from sys import stdin
from collections import defaultdict, deque

input = stdin.readline
_MAX = 2500

ipt = input().rstrip()
# start : [end_1, ...]
palindrome = defaultdict(list)

left_idx_queue = deque([])
dp = [_MAX] * len(ipt) + [0]

for idx, curr in enumerate(ipt):
    if 0 < idx:
        left_idx_queue.append(idx)
    if 1 < idx:
        left_idx_queue.append(idx - 1)

    for _ in range(len(left_idx_queue)):
        left_idx = left_idx_queue.popleft()
        if left_idx and ipt[left_idx - 1] == curr:
            palindrome[left_idx - 1].append(idx)
            left_idx_queue.append(left_idx - 1)

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

    for end in palindrome[i]:
        if dp[end + 1] + 1 < dp[i]:
            dp[i] = dp[end + 1] + 1
print(dp[0])