1695 팰린드롬 만들기 (백준, python3)

시간 제한	메모리 제한
2초	128MB

문제

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

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

입력

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

출력

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

---

풀이

하나하나 가능한 경우를 따져보며 최대 5000개 길이의 수열 arr을 팰린드롬으로 만들어보는 건 경우의 수가 너무나 많다. 하지만 어느 구간을 팰린드롬으로 만드는 비용을 구한다면 그 구간을 활용해 더 큰 구간의 팰린드롬을 만드는 비용을 얻을 수 있다.

이런 구간을 탐색한다고 해보자. i부터 j까지의 수열을 팰린드롬으로 만드는 최소 비용 dp[i][j]는 아래의 세 구간을 통해 얻을 수 있다. i~j 구간보다 작은 구간들의 최적해는 이미 구해진 상태인 것으로 생각하자. (이 가정을 반복하면 i == j인 i~j 구간의 해가 구해진 상태에서 시작하게 되는데, 이 값은 당연히 1개의 원소가 스스로 팰린드롬을 이루기 때문에 0이 된다.)

먼저 i~ j-1 구간의 최적해 dp[i][j-1]이 있다. 여기서 오른쪽에 j를 덧붙이며 arr[j]와 같은 값을 왼쪽에 하나 더하는 것으로 팰린드롬을 구성할 수 있다. 후보값은 dp[i][j-1] + 1이 된다. i+1~j 구간의 최적해를 이용한 후보값도 같은 방법으로 dp[i+1][j] + 1이 된다.
i+1~j-1 구간의 값은 약간 다른데, 만약 arr[i] == arr[j]인 경우는 dp[i+1][j-1]의 값에 새로운 원소 추가 없이 팰린드롬이 연장되므로 dp[i+1][j-1]의 값을 그대로 가져올 수 있다.

따라서 점화식을 이렇게 쓸 수 있다.

dp[i][j] = min(dp[i][j-1], dp[i+1][j]) + 1
if arr[i] == arr[j]:
    dp[i][j] = min(dp[i][j], dp[i+1][j-1])

이 과정을 반복해 dp[0][-1]의 값을 출력하면 최적해를 얻을 수 있으나
 

파이썬은 메모리 초과가 뜬다. pypy3로 제출해서 가볍게 무시해주자.

dp테이블을 길이 N의 배열 두 개로 압축하는 테크닉으로 메모리를 절약할 수 있다. 원리만 간략하게 써보면, dp[3][8]을 구성하는데 dp[3][4]나 dp[3][5]같이 탐색 중인 구간보다 2칸 넘게 짧은 구간은 쓰이지 않으므로 버려도 된다.
 

정답 코드

import sys
input = sys.stdin.readline
def solution():
    N = int(input())
    arr = list(map(int, input().split()))
    dp = [0] * N
    dp2 = [0] * N
    for k in range(1, N):
        i = N - k - 1
        for j in range(N - 1, k - 1, -1):
            dp2[j] = dp[j]
            if arr[i] == arr[j]:
                dp[j] = dp2[j - 1]
            else:
                dp[j] = min(dp[j], dp[j - 1]) + 1
            i -= 1
    print(dp[-1])
solution()