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

문제

문제 설명

• 문자열이 주어졌을 때 팰린드롬을 만족하는 부분 문자열로 분할하려고 한다.
• 부분 문자열의 개수 최솟값을 반환

풀이

• 10942 팰린드롬? 풀이에서 시작 인덱스와 끝 인덱스에 따른 팰린드롬 여부를 반환하는 알고리즘을 작성한 적이 있다.
• 이를 활용하여 dp를 사용하면 된다.
• 각 dp의 원소 값은 해당 인덱스까지의 최소 분할 값이다.
• start, end index가 주어졌을 때, 문자열[start][end]가 팰린드롬을 만족한다면, dp[end]에 기록된 값과 dp[start-1] + 1과 비교하여 최솟값을 기록한다.
  • dp[start-1]+1의 뜻은 start ~ end가 팰린드롬이니 1개로 카운트 하여, index 0 ~ start까지의 분할 최솟값에 더한다는 것이다.
• 반대로 팰린드롬을 만족하지 않는다면, dp[end-1]+1과 dp[end]를 비교한다.
  • 0 ~ end-1 까지의 분할 최솟값에다가 dp[end] 단일 원소 그 자체가 팰린드롬이니 1을 더한다는 것이다.

import sys

sys.setrecursionlimit(10 ** 8)


string = sys.stdin.readline().rstrip()
n = len(string)
palindrome = [[0 for _ in range(n)] for _ in range(n)]
dp = [2500] * (n+1)
dp[-1] = 0
for i in range(n):
    palindrome[i][i] = 1

for i in range(n - 1, -1, -1):
    for j in range(i + 1, n):
        if string[i] == string[j]:
            if j - i == 1:
                palindrome[i][j] = 1
            else:
                palindrome[i][j] = palindrome[i + 1][j - 1]

for end in range(n):
    for start in range(end + 1):
        if palindrome[start][end]:
            dp[end] = min(dp[end], dp[start-1]+1)
        else:
            dp[end] = min(dp[end], dp[end - 1] + 1)
print(dp[n-1])