[백준][1509][Python 파이썬][G1] 팰린드롬 분할

문제

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

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

입력

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

출력

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

 

 

테스트케이스

BBCDDECAECBDABADDCEBACCCBDCAABDBADD	AABDBA	ABCDEFGH	QWERTYTREWQWERT
22	2	8	5

 

코드

import sys

cmd = list(sys.stdin.readline().rstrip())

N = len(cmd)

dp = [[0 for i in range(N)]for j in range(N)]

for i in range(N):

    dp[i][i] = 1

for i in range(N-1):

    if cmd[i] == cmd[i+1]:

        dp[i][i+1] = 1

for s in range(N-3, -1, -1):

    for e in range(s+2, N):

        if dp[s+1][e-1] == 0:

            continue

        if cmd[s] == cmd[e]:

            dp[s][e] = 1

ansdp = [0]

for i in range(N):

    temp = 10000

    for j in range(i+1):

        if dp[j][i] == 0:

            continue

        temp = min(temp, ansdp[j] + 1)

    ansdp.append(temp)

print(ansdp[N])

 

후기

그리디하게.. 앞에서부터 가장 긴 펠린드롬을 떼네볼까?
그럼 최악의경우 O(N^2)니가 6250000번..
팰린드롬 검사는? O(N/2) 니까 O(N^3/2) 78억번.. 무린데
팰린드롬 검사를 빨리하거나 더 좋은 방법을 찾거나
예전에 이용했던 그 분할방법..? 되나? (예전에 풀었던 G4 팰린드롬? https://www.acmicpc.net/problem/10942)

그때의 아이디어 이용해서 i~j번째가 팰린드롬인지 검사를 다 끝내두고

그리디하게 앞에서부터 가장 긴 팰린드롬을 빠바바박 먹였더니

첫번째 TC에서 23이 나왔다.

왜그러나 잘 살펴보니

AABDBA

이와같이 AA / BDBD / A 보다 A / ABDBA 로 뒤에 양보하는게 좋은 경우가 생김

그럼 뭐다? 또 DP지 뭐...

DP로 잘 버무려서 완성