Baekjoon 1509. 팰린드롬 분할 / Python

1509. 팰린드롬 분할

난이도 : 골드 1
소요 시간 : 40분
날짜 : 2024.12.25
언어 : 파이썬
알고리즘 유형 : dp

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 문자열이 주어진다 (길이 <= 2500)
2. 문자열을 팰린드롬으로 분할한다.
3. 분할 개수의 최솟값을 구한다.

2. 해결 방식

1. dp를 두개 활용했다.
2. 팰린드롬 dp : dp_pldm[i][j] = i인덱스부터 j인덱스까지 팰린드롬인가?의 여부
   • 길이 1, 길이 2인 팰린드롬을 먼저 저장한다.
   • 길이 3이상인 경우 dp 알고리즘을 활용한다. -> 시작, 끝이 같고, 내부가 팰린드롬이면 팰린드롬
   • 이렇게 하면 모든 경우의 수를 찾을 수 있음.
3. 분할수 dp : dp_res[i] = 0번 부터 i번 까지 팰린드롬 최소 분할 수
   • dp값을 모두 0으로 해준다.
   • 끝점(j)의 인덱스를 0부터 문자열의 길이까지 탐색한다.
   • 시작점(i)은 0 부터 끝점 인덱스까지 탐색
   • i~j가 팰린드롬인 경우에만 값을 갱신, 이 경우에 이미 존재하는 dp 값이 i-1번째의 dp값보다 같거나 작으면, 갱신할 필요가 없다.

3. 정답 코드

import sys
sys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt", "r")

# input = sys.stdin.readline

from collections import deque as dq

s = list(input().strip())
l = len(s)
dp_pldm = [[0] * l for j in range(l)] # dp_pldm[i][j] = i인덱스 ~ j인덱스가 팰린드롬 인가?

dp_pldm[0][0] = 1
for i in range(1, l):
    dp_pldm[i][i] = 1    # 길이 1 팰린드롬
    if s[i] == s[i - 1]:
        dp_pldm[i - 1][i] = 1  # 길이 2 팰린드롬

for k in range(3, l + 1):   # 길이 3이상 팰린드롬 찾기
    for i in range(l - k + 1):  # 길이 k, 시작점 i
        j = i + k - 1
        if s[i] == s[j] and dp_pldm[i + 1][j - 1]:
            dp_pldm[i][j] = 1

dp_res = [0] * (l) # 0 ~ i 까지 분할 최소값

for j in range(l):  # 끝점 j
    for i in range(j + 1):  # 시작점 i
        if dp_pldm[i][j]:
            if dp_res[j] and dp_res[j] <= dp_res[i - 1]:continue
            dp_res[j] = dp_res[i - 1] + 1

print(dp_res[l - 1])