[백준 1509] 팰린드롬 분할

글에 개요

백준 알고리즘 1509번 "팰린드롬 분할" 문제입니다.

이 문제는 앞 선 팰린드롬 문제 해결을 바탕으로 한 가지 IDEA만 추가해서 해결하는 것이 중요합니다.

팰린드롬 또한 대기업의 알고리즘 SW TEST에도 기본적으로 활용되기 때문에 꼭 풀어보는 것을 추천드립니다.

혹시 어느 곳에서 나왔는지 궁금하신 분은 댓글로 남겨주시면 따로 알려드리겠습니다!!

[백준 1509] 팰린드롬 분할: https://www.acmicpc.net/problem/1509

참고할 글

1. [백준 10942] 팰린드롬?] : http://brenden.tistory.com/27

핵심 내용

▷ D[i] = i 번째 문자열까지를 팬린드롬 분할 했을 때, 분할의 최소 개수

▷ D[i] = min(D[j-1]) + 1 (i~j는 팰린드롬)

▷ i~j까지 팰린드롬은 1개, 그리고 그 이전까지의 팰린드롬 조합의 최소값

해결 방법

1. 1509번의 코드를 기반으로 작성한다.
2. 1번 인덱스부터 계산하기 위해 13line에 String에 변화를 주었습니다.
3. 25line부터 34line까지가 위의 핵심내용을 바탕으로 작성한 코드입니다.
4. 29line의 경우 d[i] == 0일 때 아무값도 들어가 있지 않는다는 말이기 때문에 한 자리 팰린드롬이 있을 것이기 때문에 조건에 넣어주어 초기화를 해줘야 됩니다.

해결한 코드

백준 내용 참고

팰린드롬 분할 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	2699	1130	788	45.209%

문제

세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다.

예를 들어, ABACABA를 팰린드롬 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}가 된다.

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

입력

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

출력

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

예제 입력 1 

BBCDDECAECBDABADDCEBACCCBDCAABDBADD

예제 출력 1 

22