[백준][파이썬][팰린드] 2079번: 팰린드롬

관련 문제들

 

문제:https://www.acmicpc.net/problem/2079

 

이 정도 난이도는 똑같은 문제가 나와도 못풀겠다. 

더 공부하지 말고 이 정도 난이도는 그냥 넘어가자

 

문제

팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다.

만일 어떤 단어가 팰린드롬이 아니라면, 그 단어는 여러 개의 팰린드롬으로 나누어질 수 있을 것이다. 단어가 주어졌을 때 이를 여러 개의 팰린드롬으로 나누되, 나누어진 팰린드롬의 개수가 최소가 되도록 나누려고 한다.

예를 들어 abaccbcb라는 문자는 aba, cc, bcb와 같이 세 개의 문자열로 나누면 각각 팰린드롬이 된다. 하지만 두 개의 문자열로 나누어서는 결코 각각이 모두 팰린드롬이 될 수 없다. 따라서 이 경우의 답은 3이다. 마찬가지로 anavolimilana와 같은 문자열은 ana, v, o, limil, ana의 다섯 개의 문자열로 나누면 각각 팰린드롬으로 만들 수 있으며, 네 개로 나누어서는 각각이 모두 팰린드롬이 되도록 만들 수 없다. 따라서 이 경우의 답은 5이다.

문자열이 주어졌을 때, 이 문자열을 최소 개수의 팰린드롬으로 나누는 프로그램을 작성하시오. 문자열 자체가 팰린드롬이라면 굳이 나눌 필요는 없다.

입력

첫째 줄에 단어가 입력으로 들어온다. 단어는 영어 소문자로만 이루어져 있으며, 그 길이는 2,000을 넘지 않는다.

출력

주어진 문자열을 최소 개수의 팰린드롬으로 나누었을 때, 그 개수를 출력한다.

예제 입력 1 

anaban

예제 출력 1 

2

예제 입력 2

abaccbcb

예제 출력 2 

3

 

 

 

---

 

import sys 
sys.stdin=open('input.txt', 'r')


def solution(word):
    N = len(word)
    
    # 팰린드롬 여부를 저장할 2차원 배열
    is_palindrome = [[False] * N for _ in range(nN)]
    
    # 1. 팰린드롬 여부 계산
    # x번째부터 j번째까지 단어가 팰린드롬인지 표시하는 방법 
    #  is_palindrome[x][y]=True
    for i in range(N):
        is_palindrome[i][i] = True  # 길이가 1인 문자열은 무조건 팰린드롬
        
        # 길이가 2인 문자열이 팰린드롬이려면 둘이 똑같아야함 aa, bb 같이 
        if i < N - 1 and word[i] == word[i + 1]:  
            is_palindrome[i][i + 1] = True
    
    # 길이가 3 이상인 문자열에 대해 팰린드롬 여부 계산
    # 세번째 글자부터 마지막 글자까지 
    for length in range(3, N + 1):  # length는 부분 문자열의 길이
        for i in range(N - length + 1):
            j = i + length - 1
            if word[i] == word[j] and is_palindrome[i + 1][j - 1]:
                is_palindrome[i][j] = True
    
    # 2. DP 테이블 채우기
    # DP 배열 (dp[i]는 문자열 s[0:i+1]까지 팰린드롬으로 나눌 때의 최소 개수)
    dp = [float('inf')] * N
    
    for i in range(N):
        if is_palindrome[0][i]:  # s[0:i+1]이 팰린드롬이면 나눌 필요 없음
            dp[i] = 1
        else:
            for j in range(i):
                if is_palindrome[j + 1][i]:
                    dp[i] = min(dp[i], dp[j] + 1)
    
    return dp[-1]

if __name__=="__main__":
    word=input()
    
    print(solution(word))