[백준]팰린드롬 분할 #팰린드롬

1. 풀이

(1) dp[i][j] = i에서 j까지의 문자가 팰린드롬이 가능하면 1, 그렇지 않으면 0. 

(2) count[i] = i번째 문자까지의 분할의 개수의 최솟값

여기서 count[i]를 구하는법이 이문제의 핵심이다. i를 구하는 법은 다음과 같다.

 

---------------------------------------------------------------------------

count[i] =

j가 1부터 i까지 도는데 이때 

i) j부터 i까지가 팰린드롬이면 => count[j-1]+1 

ii) j부터 i까지 팰린드롬이 아니면 => count[j-1]+i-j+1 

---------------------------------------------------------------------------

 

2. 소스코드

INF=9876543210

word=input()
size=len(word)
L=[[1 for j in range(size)] for i in range(size)]

# L[i][j]=1 : i에서 j가 팰린드롬이면 1
for j in range(1,size):
    for k in range(size-j):
        if word[k]==word[j+k] and L[k+1][j+k-1]==1:
            L[k][j+k]=1
        else:
            L[k][j+k]=0

minL=[i for i in range(size+1)]
for j in range(1,size):
    for i in range(j,-1,-1):
        if L[i][j]==1:
            minL[j+1]=min(minL[j+1],minL[i]+1)
        else:
            minL[j+1]=min(minL[j+1],minL[i]+j-i+1)
print(minL[size])