백준_1509_팰린드롬 분할

문제

1509번: 팰린드롬 분할

풀이

1) 분할된 팰린드롬의 최소 개수

문자열 ABACA가 주어졌을 때 해당 위치 안에서 찾은 팰린드롬을 아래처럼 표현할 수 있다.

각 위치에서 분할된 펠린드롬의 최소 개수를 저장하면, 문자열 전체에서 분할된 팰린드롬의 최소 개수를 저장할 수 있다.

dp[e] = min(dp[s]+1, dp[e])

• 팰린드롬의 최소개수를 dp로 구하는 풀이(시간초과)

def isPal(s, e) :
    while s<e :
        if word[s] != word[e-1] : return False
        s, e = s+1, e-1
    return True

word = input()
size = len(word)
dp = [float('inf') for i in range(size+1)]
dp[0] = 0 # s=0일때, 0에 접함. 그래서 dp[0]을 초기화

for e in range(1, size+1) :
    for s in range(e) :
        if isPal(s, e):
            dp[e] = min(dp[s]+1, dp[e])
print(dp[-1])

2) 팰린드롬 찾기

위 그림처럼 팰린드롬을 찾게 되면, O(N^3)의 복잡도를 가져 시간초과가 난다. 이를 해결하기 위해 팰린드롬을 판정하는 방법에 한번더 dp를 사용했다.

어떤 문자열 ABCDEF.....□ 가 주어졌을 때, 다음의 조건 하에서해당 문자열은 팰린드롬이라고 할 수 있다.

• 문자열의 처음과 끝이 같고 (A == □)
• 중간에 낀 문자열이 팰린드롬이다. (BCDEF.....이 팰린드롬)

이를 1번에 적용해보면, ABACA가 팰린드롬인지 판단하는 방법은 아래와 같다.

• 문자열의 처음과 끝이 같고 (A == A)
• 중간에 낀 문자열(BAC)이 팰린드롬인가?

여기서 다시 BAC에 대해 팰린드롬 여부를 판단해야 하는데, 이전 iteration에서 BAC에 대해 팰린드롬 여부를 판단한 적이 있다. 이를 이용해, 팰린드롬 여부를 판단할 때마다 그 값을 저장해두고 가져다 사용하면 O(N^2)로 복잡도를 줄일 수 있다.

코드

def isPal(s, e) :
    if e-s == 1 : return True*1
    if e-s <= 3 : return (word[s] == word[e-1])*1
    return (word[s] == word[e-1]) * palBoard[s+1][e-1]

word = input()
size = len(word)
palBoard = [[1 if e-s == 1 else 0 for e in range(size+1)] for s in range(size)]
dp = [float('inf') for i in range(size+1)]
dp[0] = 0

for e in range(1, size+1) :
    for s in range(e) :
        palBoard[s][e] = isPal(s, e)
        if palBoard[s][e] :
            dp[e] = min(dp[s]+1, dp[e])
print(dp[-1])