[백준/c++] 1509번 - 팰린드롬 분할

문제

https://www.acmicpc.net/problem/1509

문제

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

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

입력

첫째 줄에 문자열이 주어진다. 이 문자열의 최대길이는 2,500이다.

출력

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

풀이과정

1.규칙

• dp이므로 점화식과 메모이제이션을 이용합니다.
• 문자열을 분할할 수 있는 최솟값을 출력합니다.

2.순서

팰린드롬?(https://it-and-life.tistory.com/137)에서 약간 변형된 문제로, 문자열을 어떻게 최솟값의 팰린드롬으로 나눌수 있는지를 구하라는 문제였습니다.

예를들어 BBC라면, 최소한으로 나눌 수 있는 경우는 {BB},{C}로 2가지 입니다. {C}하나인 문자열도 팰린드롬으로 취급하기 때문입니다.(결국 자기자신은 무조건 팰린드롬으로 취급해야 합니다.)

먼저 2차배열을 만들고 문자열안에 팰린드롬이 있는경우를 체크해둡니다.

pld[3][3]	1	2	3
1	pld[1][1]=B,B=1	pld[1][2]=B,B=1	pld[1][3]=B,C=0
2	pld[2][1]=0 (이미 p[1][2]=1 이므로 변경X)	pld[2][2]=B,B=1	pld[2][3]=B,C=0
3	pld[3][1]=C,B=0	pld[3][2]=C,B=0	pld[3][3]=C,C=1

팰린드롬일 경우(빨간네모)에만 갯수를 +1증감해주되 dp를 이용해 최솟값을 유지해야 합니다.

pld[0][0] = dp[0] = 0

pld[1][1] = B,B(자기 자신은 팰린드롬. dp[0]+1 이라 생각합니다.) = dp[1] = 1

pld[1][2] = B,B(팰린드롬이므로, dp[0]+1이라 생각합니다.) = dp[2] = 1

pld[2][2] = B,B(팰린드롬이므로, dp[1]+1이라 생각합니다. 그러나 dp[1]+1=2 > dp[2] = 1이기에 최솟값을 유지해야 하므로 1을 유지합니다.) = dp[2] = 1

pld[1][3] = B,C(팰린드롬X)

pld[2][3] = B,C(팰린드롬X)

pld[3][3] = C,C(팰린드롬이므로, dp[2]+1이라 생각합니다.) = dp[3] = 2

정답인 2를 유추했으므로,

점화식은 (i : 1~(N-1) , j : 1~i) 일때 pld[j][i]가 팰린드롬일 경우, dp[i] = min(dp[i], dp[j-1]+1) 가 됩니다.

3.코드