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

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

문제

세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.

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

입력

첫째 줄에 문자열이 주어진다. 이 문자열은 알파벳 대문자로만 이루어져 있고, 최대 길이는 2,500이다.

출력

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

---

풀이

일차원 dp를 이용하는 O(n^3) 풀이는 생각하기 쉽다.

다음은 그 코드를 적어놓은 것이다.

 

S = input()
N = len(S)
dp = [0]*N

def is_palindrome(s):
    if s == s[::-1]:
        return True
    else:
        return False

dp[0] = 1
for i in range(1, N):
    tmp = 8371234974123
    for j in range(i, -1, -1):
        if is_palindrome(S[j:i+1]):
            tmp = min(tmp, dp[j-1] + 1)
    dp[i] = tmp

#print(dp)
print(dp[-1])

 

당연히 시간초과가 난다. N이 최대 2500이기 때문에...

여기서 문제가 되는 부분은 is_palindrome 함수에서만 O(n)을 쓴다는 것이다.

그래서 우리는 is_palindrome 함수를 최대한 O(1)에 근접하게 하기 위해 두 번째 dp 테이블을 정의하도록 한다.

 

바로 p[i][j] = True이면 S[i:j+1]은 팰린드롬, False면 팰린드롬이 아닌 2차원 리스트를 만드는 것이다.

 

맨 처음에는 None(둘 다 아닌 값)으로 초기화하고, 탐색을 진행하면서 True 또는 False로 값을 정해나가고, 재사용해나가는것이다.

 

더 간단하게 하는 방법도 있겠지만 일단 나는 이렇게 생각나는대로 함수를 적용해보았다. 작동은 잘 될 것이다.

def is_palindrome(i, j):
    #이미 있는 값이면
    if p[i][j] != None:
        return p[i][j]

    #길이가 1이면:
    if i == j:
        p[i][j] = True
        return True

    #길이가 2이면:
    if i+1 == j:
        if S[i] == S[j]:
            p[i][j] = True
            return True
        else:
            p[i][j] = False
            return False

    #양끝 문자열이 다르다면
    if S[i] != S[j]:
        p[i][j] = False
        return False

    #양끝 문자열이 같다면
    if is_palindrome(i+1, j-1):
        p[i][j] = True
        return True

    else:
        p[i][j] = False
        return False

 

이제 최종 코드이다.

 

S = input()
N = len(S)
dp = [0]*N

#p[i][j] = True이면 S[i:j+1]은 팰린드롬임
p = [[None]*N for _ in range(N)]

def is_palindrome(i, j):
    #이미 있는 값이면
    if p[i][j] != None:
        return p[i][j]

    #길이가 1이면:
    if i == j:
        p[i][j] = True
        return True

    #길이가 2이면:
    if i+1 == j:
        if S[i] == S[j]:
            p[i][j] = True
            return True
        else:
            p[i][j] = False
            return False

    #양끝 문자열이 다르다면
    if S[i] != S[j]:
        p[i][j] = False
        return False

    #양끝 문자열이 같다면
    if is_palindrome(i+1, j-1):
        p[i][j] = True
        return True

    else:
        p[i][j] = False
        return False

dp[0] = 1
for i in range(1, N):
    tmp = 999999
    for j in range(i, -1, -1):
        if is_palindrome(j, i):
            tmp = min(tmp, dp[j-1] + 1)
    dp[i] = tmp

print(dp[-1])

is_palindrome() 함수를 점점 발전해나가는 과정이다. 푸는데 20분밖에 안걸렸다.