[Python] 백준 1509번: 팰린드롬 분할

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

1509번: 팰린드롬 분할

 

import sys
sys.setrecursionlimit(200000)

input = sys.stdin.readline
NOT_INITIALIZED, TRUE, FALSE = 0, 1, 2


def getMinCount():
    todo = [0]

    for c in range(input_len+1):
        nextTodo = []

        while todo:
            start = todo.pop(0)

            if start >= input_len:
                return c

            for e in range(input_len-1, start-1, -1):
                if setIsPalindrome(start, e) == TRUE and c+1 < dp[e+1]:
                    dp[e+1] = c + 1
                    nextTodo.append(e+1)

        todo = nextTodo


def setIsPalindrome(start, end):
    # Base case
    if start >= end:
        isPalindrome[start][end] = TRUE
        return TRUE

    # Recursive case
    if input_str[start] != input_str[end]:
        isPalindrome[start][end] = FALSE
        return FALSE

    # 초기화
    if isPalindrome[start][end] == NOT_INITIALIZED:
        isPalindrome[start][end] = setIsPalindrome(start+1, end-1)

    return isPalindrome[start][end]


if __name__ == '__main__':
    # 입력
    input_str = str(input().rstrip())
    input_len = len(input_str)

    # 처리
    dp = [input_len+1]*(input_len+1)
    isPalindrome = [[NOT_INITIALIZED]*input_len for _ in range(input_len)]

    minCount = getMinCount()

    # 출력
    print(minCount)

 

 

나는 DP를 2개를 써서 풀었다.

 

먼저 팰린드롬에 대한 DP가 필요하다. isPalindrome[a][b]에 a~b가 팰린드롬인지를 저장한다. 여기에 DP를 쓰는 이유는 같은 범위에 대한 DP를 여러 번 반복하게 되기 때문이다. setIsPalindrome(start, end)를 호출하게 되면, 해당 범위 문자열이 팰린드롬인지를 체킹하여 결과를 반환한다. 동시에 재귀 함수이며, isPalindrome 값에 적절한 값을 대입한다.

가령, ABCAAAADBA의 범위에 해당 함수를 호출했다고 하자. isPalindrome은 AB ~ BA에 대해 TRUE 값을 넣게 되고, C~D에 대해 FALSE값을 넣고, 최종적으로 함수에서는 FALSE를 반환한다.

 

다음은 getMinCount() 함수에 대한 설명이다. c(카운트)를 늘려가면서 BFS를 사용한다. 팰린드롬을 체크하여 가능한 모든 경우를 추가하는 식이다. 가령 예시 입력 1에서, 초반에 BB가 있다. 여기서 nextTodo에 1, 2를 추가하게 된다. 1은, B가 팰린드롬이기 때문에 추가된 것으로, 다음에는 뒤에 있는 B부터 탐색을 하겠다는 것이다. 2는 당연히 BB가 팰린드롬이어서 추가한 것이다.

이 탐색에서 현재 탐색 중인 start가 input_len 이상이면 바로 현재 c를 리턴해줌으로써 출력값을 함수 밖으로 보내준다. 해당 조건은 입력 문자열을 탐색하다가, 문자열 끝까지 가게 된 경우를 뜻한다.

다음으로 반복문을 돌면서, start~e까지의 팰린드롬 여부와, DP를 체킹하여, 다음에 탐색할 값을 추가해준다. 그리고 dp 리스트는 이 BFS 탐색을 통해 c가 최소인 것들만 저장한다. 즉, DP[5] = 3라고 하면, 인덱스 5까지 오는 데에 3개의 팰린드롬을 거쳤다는 것이다.