문제
풀이
동적계획법을 활용한 문제이다. 팰린드롬이란 앞에서 읽었을 때와 뒤에서 읽었을 때 같은 문자열을 의미한다.
palindrome[][] 이중 리스트를 선언한다. palindrome[start][end]는 start에서 end까지 문자열이 팰린드롬인지 아닌지 bool형의 이중 리스트다.
문자열이 한 개인 경우는 모두 펠린드롬이므로 palindrome[1][1], palindrome[2][2] …는 모두 true이다.
문자열이 두 개인 경우는 서로 문자가 같으면 true이다.
문자열이 세 개이상인 경우 맨 처음 문자와 맨 끝 문자가 같은 경우 나머지 문자열이 팰린드롬이면 그 문자열은 팰린드롬이다.
그렇게 팰린드롬 이중 리스트를 작성하고, 최소 갯수를 저장하는 dp 리스트를 선언한다.
dp[A] = B는 A까지 문자열의 팰린드롬 최수 갯수가 B개라는 의미이다.
start와 end까지 팰린드롬이라면 dp[start-1]+1이 최소 갯수가 될 후보이다. 기존의 값과 비교하여 계속해서 최솟값을 갱신한다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import sys
from math import *
string = ['a']
input = input().strip() # string : 0 ~ len(string)-1
string.extend(input)
length = len(string)-1 # 0번째 index의 갯수 제거
palindrome = [[0 for _ in range(0, length+1)] for _ in range(0, length+1)] # 0~len(string)
for i in range(1, length+1): # 1 ~ len(string)
palindrome[i][i] = True
# 1개는 다 palindrome
for i in range(1, length): # 0 ~ len(string)-1
if(string[i] == string[i+1]):
palindrome[i][i+1] = True
# 2개 문자에서 서로 같으면 palindrome
for len in range(3, length+1): # 문자열의 길이가 3 ~ len(string)까지
for init in range(1, length-len+1+1): # 시작 index가 0 ~ len(string)-len+1까지 Ex)string -> 5글자, len -> 3이면, init index는 3까지
if(string[init] == string[init+len-1]):
if(palindrome[init+1][init+len-1-1] == True):
palindrome[init][init+len-1] = True
# 3개 이상 문자에서 처음과 끝의 문자가 같고, 그 나머지가 palindrome이면 그 문자는 palindrome
dp = [0 for _ in range(0, length+1)] # 0~len(string)
for end in range(1, length+1):
dp[end] = 2e9
for start in range(1, end+1): # 1 ~ end
if(palindrome[start][end] == True):
dp[end] = min(dp[end], dp[start-1]+1)
print(dp[end])
