[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 1509번 _ 팰린드롬 분할

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

1509번: 팰린드롬 분할

[문제]

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

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

 

[입력]

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

[출력]

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

 

[아이디어]

1) i번째부터 j번째까지의 문자열이 팰린드롬인지를 dp에 관리한다. (0 or 1)

2) i번째 위치까지의 팰린드롬 분할의 최댓값은 i이다.

3) 1 ~ n(문자열의 길이)의 배열을 시작으로, i번째까지 팰린드롬 분할의 최소는 아래의 경우 중 하나이다.

① 추가되는 i번째 문자가 앞선 문자들과의 팰린드롬과는 무관하여, 홀로 별도의 분할이 되는 경우

-> 이 경우 이전까지의 팰린드롬 분할의 최소 + 1이다.

② 추가되는 i번째 문자가 앞선 문자들과의 팰린드롬을 형성하는 경우

-> 이전까지의 팰린드롬 분할의 최소보다 작아질 수 있다.

4) 3)의 모든 케이스를 커버하기 위해, i=1~n에 대해 i보다 큰 j에 대한 반복문을 돌리면서, i부터 j까지의 문자열이 팰린드롬을 이루면(dp[i][j]==1) j번째까지의 팰린드롬 분할의 최소를 i이전까지의 최소(ans[i-1]) + 1로 업데이트한다.

 

s = ' ' + input()
n = len(s) -1

dp = [[0]*(n+1) for _ in range(n+1)]
ans = list(range(n+1))

for i in range(n):
    for k in range(1,n+1-i):
        if i ==0:
            dp[k][k] = 1
        elif i==1 and s[k]==s[k+1]:
            dp[k][k+1] = 1
        else:
            if s[k]==s[k+i] and dp[k+1][k+i-1]==1:
                dp[k][k+i]=1
                
for i in range(1, n+1):
    ans[i] = min(ans[i], ans[i-1] + 1)
    for j in range(i+1, n+1):
        if dp[i][j]:
            ans[j] = min(ans[j], ans[i-1] + 1)