본문으로 바로가기

[백준 1509] 팰린드롬 분할

category 알고리즘/백준 알고리즘 2018. 4. 19. 20:18
글에 개요

백준 알고리즘 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 MB2699113078845.209%

문제

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

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

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

입력

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

출력

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

예제 입력 1 

BBCDDECAECBDABADDCEBACCCBDCAABDBADD

예제 출력 1 

22


'알고리즘 > 백준 알고리즘' 카테고리의 다른 글

[백준 11052] 붕어빵 판매하기  (0) 2018.04.20
[백준 9095] 1, 2, 3 더하기  (0) 2018.04.20
[백준 1509] 팰린드롬 분할  (0) 2018.04.19
[백준 10942] 팰린드롬?  (1) 2018.04.19
[백준 10825] 국영수  (0) 2018.04.18
[백준 10814] 나이순 정렬  (0) 2018.04.18

댓글을 달아 주세요