문제
- 앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다.
- 한 수열이 주어졌을 때, 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다.
- 최소 몇 개의 수를 끼워 넣으면 되는지 알아내기
- 1 <= N <= 5000
풀이
- dp[i][j] : i~j 문자열에서 팰린드롬으로 만들기 위해 끼워넣어야 하는 수의 개수
- dp[i][i+1] ; arr[i] 과 arr[i+1] 이 같으면 0, 다르면 1
- dp[2][4]
- arr[2] == arr[4] ; arr[3][3] 과 같음
- arr[2] != arr[4] ; arr[2][3]과 arr[3][4] 중에 더 작은 수 + 1
이대로 하면 메모리 초과가 뜸
- 사실상 2개의 연속된 행만 보면 되므로 dp 테이블을 줄인다.
import sys
input = sys.stdin.readline
N = int(input())
arr = list(map(int, input().split()))
# dp
dp = [[0]* N for _ in range(2)]
for i in reversed(range(N)) :
for j in range(i+1, N) :
row = i % 2
if arr[i] == arr[j] :
dp[row][j] = dp[row-1][j-1]
else :
dp[row][j] = min(dp[row][j-1], dp[row-1][j]) + 1
print(dp[0][-1])
References
