1509. 팰린드롬 분할

1509번: 팰린드롬 분할

---

문자열을 팰린드롬인 부분 문자열로 나눠야 한다. 

 

$solve(i)$를 $[i, len]$ 구간의 정답으로 정의하자.

이 값은 $[i, len]$이 팰린드롬이라면 1, 그렇지 않다면 $min_{j=i}^{len} (1 + solve(j))$이다. 물론 $[i, j]$ 부분 문자열은 팰린드롬이어야 한다.

 

단, 중복 계산을 방지하기 위해 $solve(i)$의 값을 배열에 저장해야 한다(메모이제이션).

그리디가 안 되는 이유

예제: AABDBA

위의 예제에서 $0$번에서 시작하는 가장 긴 팰린드롬은 $[0, 1]$의 AA이다. 같은 방식으로 문자열을 나누면 {AA, BDB, A}가 된다. 그런데 정답은 {A, ABDBA}이다. 즉 현재 위치에서 시작하는 가장 긴 팰린드롬을 선택하면 안 된다는 것이다.

 

문제를 이해했다면 이제 코드를 작성해 보자.

 

스포일러 주의!

# 시간 초과를 받는 이유

$[i, j]$ 구간이 팰린드롬인지 확인하는 작업은 $O(j - i)$가 걸린다. 이 작업을 조금 더 빨리 할 수 없을까?

 

$[i, j]$ 구간이 팰린드롬이려면 $s_{i} = s_{j}$이고 $[i+1, j-1]$ 구간이 팰린드롬이어야 한다. 간단한 재귀 함수로 $O(len^2)$ 시간에 이 값을 계산할 수 있으며, 값을 계산한 후에는 $O(1)$에 팰린드롬 여부를 확인할 수 있다.

---

동적 계획법에 맛을 들이는 중.