[백준] No.1509 - 팰린드롬 분할 (C++)

문제

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

1509번: 팰린드롬 분할

 

풀이

일단 이전 단계인 문제 팰린드롬?을 풀고 오자.

 

이전 문제에서 우리는 start에서 end까지 팰린드롬을 이루는지의 여부를 is_palin[start][end]  저장해 문제를 해결하였다.

이번 문제에서도 해당 저장 값을 그대로 이용하자.

 

첫 글자(1)에서 현재 위치 (i)까지의 팰리드롬 개수의 최솟값을 dp[i]에 저장하자.

 

 i 번째 글자까지가 팰린드롬이지의 여부는 is_palin[1~i][i]를 확인해보면 된다.

 

is_palin[j+1][i]이 true인 경우

  j+1~i까지를 하나의 팰린드롬으로 묶어 1개의 분할을 얻는다.

 

그리고 1~j까지의 팰리드롬 분할 개수의 최솟값을 저장하는 dp[j]값을 1과 더해

 (j+1,i)를 팰린드롬 으로 묶을 때의 최솟값을 dp[j] +1로 얻을 수 있다.

 

이제 j를 0~i-1까지 순회하며 얻은 가장 작을 값이 dp[i]의 값이 된다.

따라서 dp[i] = min(dp[i], dp[j+1]+1) 이다.

 

참고로 문자열을 인덱스 1부터 시작하도록 변환하여

dp[0] = 0의 값을 미리 넣어두면

dp[2] = min(dp[2], dp[0]+1)과 같이 1~2를 하나의 팰린드롬으로 묶었을 때 이전의 글자가 더 없기 때문에, 계산이 용이해진다.

 

코드