[Python/BOJ] 1695. 팰린드롬 만들기

https://www.acmicpc.net/problem/1695

1695번: 팰린드롬 만들기

문제

앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다.

한 수열이 주어졌을 때, 이 수열에 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다. 최소 몇 개의 수를 끼워 넣으면 되는지를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 길이 N(1≤N≤5,000)이 주어진다. 다음 줄에는 N개의 수열을 이루는 수들이 주어진다. 각 수들은 int 범위이다.

출력

첫째 줄에 끼워 넣을 수들의 최소 개수를 출력한다.

풀이

Code

import sys
input = sys.stdin.readline

n = int(input())
array = list(map(int, input().split()))
# 1. DP 생성
dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
# 2.
for i in range(1, n + 1) :
    for j in range(1, n + 1) :
        # 2-1. 두 수가 같은 경우
        if array[-i] == array[j - 1] : dp[i][j] = dp[i-1][j-1] + 1
        # 2-2. 두 수가 다른 경우
        else : dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# 4. 결과 출력
print(n - dp[-1][-1])