[BOJ]1509번: 팰린드롬 분할

 

www.acmicpc.net/problem/1509

---

JusticeHui님의 풀이(justicehui.github.io/ps/2019/09/21/BOJ1509/)를 참고해서 해결했습니다.

 

1. 우선 dp를 사용하여 구간 [st, en]이 팰린드롬인지 파악할 수 있습니다.

 

2. 분할 개수의 최솟값을 구하는 것도 dp를 사용하면 됩니다.
dp2[n] = [1, n]구간을 팰린드롬으로 분할하는 최소 개수 라고 정의해보겠습니다. 
만약 [j, i] 구간이 팰린드롬이면, [1, j-1]까지 잘 분할하고, [j, i]를 팰린드롬 한 덩어리로 만들어주면 됩니다.
그러므로 dp2[i] = min(dp2[i], dp2[j-1] + 1) 점화식으로 답을 구할 수 있습니다.

(단, j <= i and [j, i]는 팰린드롬)

---

코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ1509.cc