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

바로가기 링크

문제

세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.
분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오.

입력

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

출력

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

정답코드

코드 출처: https://velog.io/@sunkyuj/python-%EB%B0%B1%EC%A4%80
의미없이 반복되는 코드를 삭제했다. dp[end] = min(dp[end], dp[end - 1] + 1)

import sys

sys.setrecursionlimit(10 ** 8)
input = lambda: sys.stdin.readline().rstrip()

s = input()
L = len(s)


dp = [2500 for _ in range(L + 1)]
dp[-1] = 0
is_palindrome = [[0 for j in range(L)] for i in range(L)]


for i in range(L):  # 길이 1 짜리 팰린드롬
    is_palindrome[i][i] = 1

for i in range(1, L):  # 길이 2 짜리 팰린드롬 (AA, DD 같은 놈들)
    if s[i - 1] == s[i]:
        is_palindrome[i - 1][i] = 1

for l in range(3, L + 1):  # 길이 3 ~ L 짜리 팰린드롬
    for start in range(L - l + 1):
        end = start + l - 1
        if s[start] == s[end] and is_palindrome[start + 1][end - 1]:
            # 처음과 끝이 같고, 그 사이가 팰린드롬이면
            is_palindrome[start][end] = 1  # start~end 도 팰린드롬

for end in range(L):
	dp[end] = dp[end - 1] + 1
    for start in range(end + 1):
        if is_palindrome[start][end]:
            dp[end] = min(dp[end], dp[start - 1] + 1)

print(dp[L - 1])

접근법

접근법을 생각하지 못해서 다른 사람의 풀이를 봐야했다.
다음에 다시 풀어보기 위해서 접근법을 정리해보자

문제의 목표는 전체 문자열을 최소 개수의 팰린드롬으로 분할하는 것이다.
전체 문자열 길이를 L, 문제의 목표를 dp[L-1] 라고 할 수 있다.

작은 목표로 분할해보자

dp[0], dp[1], ... , dp[i], ... , dp[L-1] 까지 구해야 한다.

고려해야 하는 문자열의 길이가 늘어날 때마다 고려해야 할 것은 아래 2가지이다.

1. 문자열 1개를 추가하는 것은 분할 개수가 1개 늘어나는 것이므로 dp[i] = dp[i-1]+1 로 갱신하고 시작할 수 있음을 알 수 있다.

2. 마지막으로 추가한 문자로 이전에 없던 팰린드롬이 완성되어 분할 개수가 줄어들 수 있다는 것을 고려해야 한다.

for start in range(end + 1):
	if is_palindrome[start][end]:
		dp[end] = min(dp[end], dp[start - 1] + 1)

is_palindrome[start][end]을 어떻게 알 수 있을까

is_palindrome 을 구하는 것도 DP를 사용해야한다.
어떤 문자열이 palindrome인지 확인하려면
가장 바깥 양쪽 문자가 같고 그 안의 문자열들이 palindrome인지 확인해서 알 수 있다.

따라서, 길이가 긴 문자열들의 palindrome 여부를 알려면 작은 문자열부터 구해야한다.
-> l = end - start 일 때, l 이 1인 문자열부터 L인 문자열까지 구해야 한다.

for i in range(L):  # 길이 1 짜리 팰린드롬
    is_palindrome[i][i] = 1

for i in range(1, L):  # 길이 2 짜리 팰린드롬 (AA, DD 같은 놈들)
    if s[i - 1] == s[i]:
        is_palindrome[i - 1][i] = 1

for l in range(3, L + 1):  # 길이 3 ~ L 짜리 팰린드롬
    for start in range(L - l + 1):
        end = start + l - 1
        if s[start] == s[end] and is_palindrome[start + 1][end - 1]:
            # 처음과 끝이 같고, 그 사이가 팰린드롬이면
            is_palindrome[start][end] = 1  # start~end 도 팰린드롬