팰린드롬 분할 ( 1509 번 )

1509번: 팰린드롬 분할

---

🧠 알고리즘

• DP를 이용한 ( 팰린드롬 사전 계산 + 구간 분할 최소 횟수 DP )

 

✔️ 동작 방식

[ 핵심 아이디어 ]

• 모든 구간이 팰린드롬인지 먼저 계산해 두면
  이후에는 그 구간을 한 번에 하나의 조각으로 취급할 수 있다.
• 결국 "앞에서부터 팰린드롬 단위로 최소 몇 번 자르는가?" 를 DP로 구한다.

[ 로직 요약 ]

1. 문자열의 모든 구간에 대해 팰린드롬 여부 DP로 계산
2. dp_count[end] = end까지 최소 몇 조각인지 DP로 계산
3. start~end가 팰린드롬이면 >> dp_count[end] = dp_count[start-1] + 1
4. 마지막 위치 값이 정답

---

 

🧾 코드

import sys

def _main():
    len_n = len(n)
    """
        dp[시작 위치][끝 위치]
        value = 팰린드롬 여부 ( 0: 팰린드롬 x, 1: 팰린드롬 o )
    """
    dp = [[0] * (len_n + 1) for _ in range(len_n + 1)]
    for lenth in range(1, len_n + 1):
        for start in range(1, len_n - lenth + 2):
            end = start + lenth - 1

            if lenth == 1:
                dp[start][end] = 1
            elif lenth == 2 and n[start - 1] == n[end - 1]:
                dp[start][end] = 1
            elif lenth >= 3 and n[start - 1] == n[end - 1] and dp[start + 1][end - 1] == 1:
                dp[start][end] = 1

    dp_count = [float('inf')] * (len_n + 1)
    dp_count[0] = 0

    for end in range(1, len_n + 1):
        for start in range(1, end + 1):
            if dp[start][end] == 1:
                dp_count[end] = min(dp_count[end], dp_count[start - 1] + 1)

    return dp_count[-1]
    

n = sys.stdin.readline().rstrip()
print(_main())

---

 

⏱️ 시간 복잡도

for lenth in range(1, len_n + 1) : 문자열 팰린드롬 여부 검사 ( 이차형 시간 )
    for start in range(1, len_n - lenth + 2)

해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )