[백준 1509번] 팰린드롬 분할 (Python3)

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가 잘 혼합된 재미있는 문제였다.

 

 

오늘의 교훈) 투 포인터 알고리즘은 유용하다.