BOJ 1509: 팰린드롬 분할 [Python 3]

오늘 풀어볼 문제는 팰린드롬 분할이다.

이 문제는 DP를 통해서 풀 수 있었다.

import sys
input=sys.stdin.readline

line=input()
n=len(line)
dp=[[0 for _ in range(n+1)] for _ in range(n+1)]
answer=[1e10 for _ in range(n+1)]
answer[0]=0

for i in range(1,n+1): #하나짜리는 무조건 펠린드롬
    dp[i][i]=1 

for i in range(1,n): #두칸짜리 확인
    if line[i]==line[i-1]:
        dp[i][i+1]=1

for i in range(2,n+1): #i == 길이
    for j in range(1,n+1-i): # j==시작점. (1이 처음)
        if line[j-1]==line[j+i-1] and dp[j+1][i+j-1]==1:
            dp[j][i+j]=1
for i in range(1,n+1): #시작점부터 dp 확인하면서 확인
    answer[i]=min(answer[i], answer[i-1]+1)
    for j in range(i+1,n+1):
        if dp[i][j]!=0:
            answer[j]=min(answer[j],answer[i-1]+1)
print(answer[n])

사이즈에 알맞는 dp 테이블을 만든다. 이후, 1 character, 2 characters, 3+ characters에 대해서 팰린드롬 여부를 따져서 dp에 저장한다.

당연히 한 칸 짜리는 모두 팰린드롬이다.

두 칸은, 두 칸이 서로 같으면 팰린드롬이다.

3 칸 이상의 크기이면,

양 끝의 문자가 서로 같고, 양 끝의 문자를 제외한 안 쪽에 위치한 문자열이 팰린드롬인지 확인한다.

이후 이중 for문을 이용해서 i+1부터 j까지 팰린드롬이 성립하면, 1부터 i까지의 팰린드롬의 최솟값 +1 과 이미 저장되어있는 1부터 j까지의 팰림드롬의 최솟값을 비교한다.