[알고리즘 문제풀이] 팰린드롬 분할

문제 제목 : 팰린드롬 분할

문제 난이도 : 중

문제 유형 : 동적 프로그래밍

https://www.acmicpc.net/problem/1509
시간 제한 : 2초
메모리 제한 : 128MB

문제풀이 아이디어

< 소스코드 >

text = input()
n = len(text)
dp = [0 for _ in range(n)]

table = [[False for _ in range(n)] for _ in range(n)]

for i in range(n):
    table[i][i] = True
    
for i in range(n-1):
    if text[i] == text[i+1]:
        table[i][i+1] = True
    
## 대각선 방향으로 채움
for a in range(n-2):
    for i in range(n-2-a):
        j = i + a + 2
        if text[i] == text[j] and table[i + 1][j-1]:
            table[i][j] = True
            
## dp
dp[0] = 1
for i in range(1, n):
    min_val = dp[i-1] + 1
    for j in range(i):
        if table[j][i]:
            min_val = min(min_val, dp[j-1] + 1)
    dp[i] = min_val
    
print(dp[-1])