문제링크
https://www.acmicpc.net/problem/1509
1509번: 팰린드롬 분할
세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하
www.acmicpc.net
1. 핵심
1) 유형
DP: [@+작은 팰린드롬+@] 작은 팰린드롬 양쪽의 @만 확인해서 더 큰 팰린드롬 [@+작은 팰린드롬+@] 인지 확인
2) 왜 reversed(range(n))을 할까?
IF. reveresed가 아니라 range(n)을 생각해보자.
→ 인덱스의 범위가 (0, x)가 팰린드롬을 확인하기 위해서는 작은 팰린드롬 (1, x - 1) 이 범위에서 팰린드롬인지 확인해야한다. 하지만 우리가 raneg(n)으로 시작하기 때문에 (1, x - 1)이 팰린드롬인지는 알 수가 없다.
IF. reversed(range(n))
→ 인덱스의 범위(n-8, n-4)면 팰린드롬을 확인하기 위해서는 (n-9, n-5)로 reversed로 거꾸로 접근해 팰린드롬인지 아닌지 판단 가능
3) dp[i]의 정의
→ dp[i] - 문자열[i]까지의 팰린드롬 분할의 최소값
→ 문자열의 길이가 1인 경우 반드시 팰린드롬이므로 dp 초기화 시 주의
4)≪~~≫ 가 팰린드롬이면 dp[j] + 1 도 dp[i]의 후보가 될 수 있다.
→ dp[i] = min(dp[i] , dp[j] + 1)
0 | ...... | j ( - 팰린드롬 끝) | ≪ j + 1 | ...... | i(현재위치) ≫ |
2. 코드(Python)
s = input()
n = len(s)
# s[i] ~ s[j]까지의 문자열이 팰린드롬인지 확인용!
is_palindrome = [[False for _ in range(n)] for _ in range(n)]
for l in reversed(range(n)):
is_palindrome[l][l] = True
if l + 1 < n and s[l] == s[l+1]:
is_palindrome[l][l+1] = True
for r in range(l+2, n):
if is_palindrome[l+1][r-1] and s[l] == s[r]:
is_palindrome[l][r] = True
# dp[i]의 정의: s[i]번째까의 팰린드롬 분할의 최소 수
dp = [i+1 for i in range(n)]
for i in range(n):
# 0 ~ i까지 팰린드롬인지 확인해야함!!
if is_palindrome[0][i]:
dp[i] = 1
for j in range(i):
# 1 ~ i까지 팰린드롬인지 확인!
if is_palindrome[j+1][i]:
dp[i] = min(dp[i], dp[j] + 1)
print(dp[n-1])
'PS > 백준' 카테고리의 다른 글
[DP] 호텔(Python) (0) | 2024.02.16 |
---|---|
[백준/BOJ] 4233번 - 가짜 소수 (Python) (0) | 2023.11.02 |
[백준/BOJ] 14621번 - 나만 안되는 연애 (Python) (1) | 2023.10.21 |
[백준/BOJ] 27172번 - 수 나누기 게임 (Python) (1) | 2023.10.17 |
[백준/BOJ] 1005번 - ACM Craft (Python) (1) | 2023.09.30 |