본문 바로가기
PS/백준

[백준/BOJ] 27172번 - 수 나누기 게임 (Python)

by 행복한라이언 2023. 10. 28.
728x90
반응형

문제링크

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])

 

 

728x90
반응형