Joonas' Note

BOJ 1509 - 팰린드롬 분할 본문

알고리즘/문제 풀이

BOJ 1509 - 팰린드롬 분할

joonas 2018.07.18 17:07

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

문제

\(dp[i]\) = \(i\)번째 위치에서 가능한 팰린드롬 분할의 최소 개수

\(isPaline[i][j]\) = \(i~j\) 가 팰린드롬인지 여부


예제에도 끼워져있지만 AABDBADD 와 같은 경우의 처리때문에 여러 경우를 탐색해야한다. 이것을 분할하는 경우는 아래와 같다.

A - A - B - D - B - A - D - D
A - A - B - D - B - A - DD
A - A - BDB - A - D - D
A - A - BDB - A - DD
A - ABDBA - D - D
A - ABDBA - DD
AA - B - D - B - A - D - D
AA - B - D - B - A - DD
AA - BDB - A - D - D
AA - BDB - A - DD

팰린드롬으로 최대한 묶은 후, 남은 문자열에 대해서 이 작업을 반복한다.

코드

코드보기


'알고리즘 > 문제 풀이' 카테고리의 다른 글

BOJ 1509 - 팰린드롬 분할  (0) 2018.07.18
BOJ 3079 - 입국심사  (0) 2018.05.25
BOJ 1766 - 문제집  (0) 2018.05.22
BOJ 13701 - 중복 제거  (0) 2018.05.18
BOJ 15719 - 중복된 숫자  (0) 2018.05.18
BOJ 15683 - 감시  (0) 2018.05.17
0 Comments
댓글쓰기 폼