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

정석 풀이가 아닐 수 있습니다.

문제 요약

• 팰린드롬 : ‘회문’과 같은 말로, 뒤집어도 처음과 똑같은 수열을 가리키는 말이다.

• 1 2 3 4 2에 최소의 숫자를 추가해서 팰린드롬을 만드는 문제이다.

• 이 경우 4와 2 사이에 3을, 2 다음에 1을 추가하여 1 2 3 4 3 2 1을 만들 수 있다. (추가한 숫자 2개)

풀이

• 다이나믹 프로그래밍을 이용하여 풀 수 있다.

• DP[i][j]는 i번째 글자부터 j번째 글자까지를 팰린드롬으로 만들기 위해 끼워넣어야 하는 수의 개수이다.
• 가령 DP[3][4] 는 4 2를 팰린드롬으로 만들기 위해 필요한 수이며, 이 경우 오른쪽 끝에 2를 끼워넣거나, 왼쪽 끝에 2를 끼워 넣어 1임을 알 수 있다.
• 이처럼 수열 길이가 2이고 서로 다른 수일 경우 DP[i][i+1]의 값은 1이된다.

• 다이나믹 테이블을 채워나가다가 DP[2][4]를 마주하였을 때의 경우이다.
• 결론만 말하자면 DP[i][j-1]과 DP[i+1][j] 값의 최소값을 구하여 여기에 1을 더한 숫자가 DP[i][j]의 값이 된다.

• 이유를 조금 풀어서 설명하자면, DP[2][4]는 DP[2][3], DP[4] 또는 DP[2], DP[3][4]로 쪼개어 생각할 수 있다.
• 이들은 이미 다이나믹 테이블이 알고 있는 값이며, 숫자를 1개(빨간색 숫자)만 추가하면 팰린드롬이 된다는 것이 확실하다. (2 3 2 또는 3 4 3)
• 이제 우리가 풀고자 하는 DP[2][4]는 팰린드롬의 한쪽 끝에 숫자 하나를 추가한 꼴이 된다. (2 3 2 4 또는 2 3 4 3)
• 이제 여기에 반대쪽 끝에 같은 수를 추가하면 팰린드롬이 되므로 +1을 하면 된다.
• 최소로 추가하도록 DP 값을 구해야 하므로 DP[i][j-1]과 DP[i+1][j] 중 최소값을 취하여 1을 더하면 DP[i][j]의 값이 된다.

• 이번엔 새로운 경우인데 바로 DP[i][j]에서 arr[i]==arr[j]인 경우이다.
• 마찬가지로 결로만 말하면 DP[i+1][j-1]의 값이 그대로 DP[i][j]값이 된다.

• 그 이유는 팰린드롬을 만들 때 양쪽 끝이 같기 때문에, 그냥 소거해 버릴 수 있고 결과적으로 i+1 부터 j-1 까지의 수열을 팰린드롬을 만드는 문제가 된다. 이는 이미 DP[i+1][j-1]이 알고 있으므로 그냥 값을 가져오면 된다.

• 같은 규칙을 적용하여 DP[0][-1]을 구했다면, 이것이 전체 수열을 팰린드롬으로 만들기 위해 추가해야할 수이다.

코드

• 풀이는 (N, N) 크기 이차원 행렬로 했지만 사실 (2, N) 크기의 행렬만 있어도 가능하다.

• 그 이유는 어짜피 정답은 DP[0][-1]으로 고정되어 있고, 한번에 봐야하는 행이 i와 i+1 2개이기 때문이다.

• 이렇게 행 인덱스가 짝수일 때 사용할 행과, 홀수일 때 사용할 행만 있으면 된다. 자세한 것은 코드로 확인하자.

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

dp = [[0] * N for _ in range(2)]

# 뒷부분부터 탐색해야함
for i in reversed(range(N)):
    for j in range(i+1, N):
    	# 짝수와 홀수 구분
        row = i % 2
        # 홀수행(i=1)일 때 i-1=0으로 짝수행을 가리킴, 짝수행(i=0)일 때 i-1=-1로 홀수행을 가리킴
        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