관리 메뉴

Joonas' Note

BOJ 1509 - 팰린드롬 분할 본문

알고리즘/문제 풀이

BOJ 1509 - 팰린드롬 분할

joonas 2018. 7. 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 16235 - 나무 재테크  (0) 2018.10.30
    BOJ 11058 - 크리보드  (0) 2018.09.05
    BOJ 1509 - 팰린드롬 분할  (0) 2018.07.18
    BOJ 3079 - 입국심사  (0) 2018.05.25
    BOJ 1766 - 문제집  (2) 2018.05.22
    BOJ 13701 - 중복 제거  (0) 2018.05.18
    0 Comments
    댓글쓰기 폼