[1695] 펠린드롬 만들기 (파이썬)

문제

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

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

입력

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

출력

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

==

솔루션

• 처음에는 추가한 갯수를 기준으로 최소 힙을 이용했음. => 메모리 초과
• n이 5000 이하라 O(n^2) 까지는 허용 된다고 생각함.
• 원래의 배열과 그것의 역순과의 차이가 나는 부분들이 몇 개인지 알고 그것을 전체 갯수에 빼면 추가해야 할 숫자의 갯수들이라고 생각
• 공통 된 최장 부분 수열을 구하자 => LCS 알고리즘 
• arr[j] = brr[i] 이라면 dp[i][j]   = dp[i-1][j-1] + 1
• arr[j] != brr[i] 이라면 dp[i][j] = dp[i-1][j] , dp[i][j-1] 중 최댓값

n = int(input().rstrip())
arr = list(map(int, input().rsplit()))
brr = arr[::-1]
dp = [[0]*n for _ in range(n)]
dp[0][0] = 0 if arr[0] != brr[0] else 1

for i in range(1, n):
    dp[0][i] = 1 if arr[i] == brr[0] else dp[0][i-1]

for i in range(1, n):
    for j in range(n):
        if j == 0:
            dp[i][j] = 1 if arr[j] == brr[i] else dp[i-1][j]
        else:
            if arr[j] == brr[i]:
                dp[i][j] = dp[i-1][j-1]+1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

print(n-dp[n-1][n-1])