[BOJ] 1509 팰린드롬 분할

1509번: 팰린드롬 분할

문제

세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.

분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열이 주어진다. 이 문자열은 알파벳 대문자로만 이루어져 있고, 최대 길이는 2,500이다.

출력

첫째 줄에 팰린드롬 분할의 개수의 최솟값을 출력한다.

---

DP는 오랜만이다. 역시 문제가 심플해서 고른 문제다. 문제에서는 팰린드롬이 무엇인지 자세히 설명해주지 않아서 찾아봐야 했다.

 

팰린드롬은 문자열의 첫번째와 마지막 문자가 같고 그 사이에 있는 문자열도 팰린드롬임을 만족하는 녀석이다. 정의부터가 아주 DP스럽다. 팰린드롬임을 판정하는 점화식을 세우기 위해선 초기 조건이 필요하다. 문자열의 초기 조건은 보통문자열의 길이가 1인 경우이다. 이 경우엔 팰린드롬임을 만족한다. 그리고 길이가 2인 경우엔 맨 앞과 맨 끝의 문자열이 같은 지 검사해주면 된다. 길이가 3 이상인 경우부터는 점화식을 세워서 팰린드롬을 판정했다. 문자열에서 시작 위치와 끝 위치를 골라 팰린드롬임을 판정하는데에는 O(N^2)이 걸린다. 문자열의 최대 길이가 2500이므로 N^2여도 가능하다. 

 

팰린드롬 판정이 끝난 이후엔 최소 분할 횟수를 구하기 위해서 또 다른 점화식이 필요하다. DP[i]는 문자열의 i번째까지 최소 분할 횟수를 저장한다. 따라서 문제에서 원하는 정답은 DP[N]에 저장되게 된다. 이전에 구했던 팰린드롬 정보를 이용해서 만약 검사하는 위치가 팰린드롬임을 만족하는 경우엔 DP 값을 업데이트해준다.

 

 

후기)

DP를 별로 선호하지 않았는데 오랜만에 보니까 이정도면 양반이다.