import sys
input = sys.stdin.readline
INF = 10**9
seq = input().strip()
N = len(seq)
palin = [[] for i in range(N)]
start,end = 0,0
while True:
if end == N:
break
s,e = start,end
if seq[s] == seq[e]:
while True:
palin[e].append(s)
s1 = s-1
e1 = e+1
if not (s1>=0 and e1<N):
break
if seq[s1] != seq[e1]:
break
s,e = s1,e1
if start == end:
end += 1
else:
start += 1
DP = [INF]*(N+1)
DP[0] = 0
for end in range(N):
for start in palin[end]:
DP[end+1] = min(DP[end+1],DP[start]+1)
print(DP[-1])
이전에 팰린드롬? 문제를 풀때는 투 포인터 알고리즘을 몰랐었는데, 알게된 지금의 나에겐 너무나 쉬운 문제
일단 투 포인터 알고리즘을 이용해서 모든 팰린드롬을 구하는데, 이때 끝나는 점을 기준으로 구한다.(DP에 이용하기 위해서)
끝나는 점의 리스트에 팰린드롬을 이루는 시작지점을 저장한다.
각 지점에 대해서 최소 분할수에 대한 DP를 한다. 아까 구한 각 엔드지점의 스타트지점보다 1 작은 DP값 중 최솟값에 +1을 한게 곧 해당 지점의 최솟값이다.
투포인터와 DP가 잘 혼합된 재미있는 문제였다.
오늘의 교훈) 투 포인터 알고리즘은 유용하다.