C++ 회문 제거: 구간 DP로 최소 이동 횟수 구하기

문제 개요

정수 배열 arr가 주어집니다. 한 번의 이동(move)으로 인덱스 i부터 j까지(i <= j) 구간에 해당하는 회문(palindrome) 부분 배열을 선택하여 제거할 수 있습니다. 이때 부분 배열을 제거하면 남아 있는 왼쪽과 오른쪽 요소들이 서로 붙어 빈 공간을 메운다는 점에 유의해야 합니다.

목표는 배열의 모든 숫자를 제거하기 위해 필요한 최소 이동 횟수를 구하는 것입니다.

예시

입력이 arr = [1, 3, 4, 1, 5]라면 출력은 3입니다. 다음 순서로 제거하면 되기 때문입니다.

1. [4] 제거 → 배열은 [1, 3, 1, 5]가 됩니다.
2. [1, 3, 1](회문) 제거 → 배열은 [5]가 됩니다.
3. [5] 제거 → 배열이 비게 됩니다.

접근 방법: 구간 동적 계획법(DP)

이 문제는 구간 DP(Interval DP)로 해결할 수 있습니다. dp[i][j]를 "인덱스 i부터 j까지의 구간을 모두 제거하는 데 필요한 최소 이동 횟수"로 정의하고, 구간의 길이를 1부터 n까지 순서대로 늘려 가며 값을 채워 나갑니다.

점화식은 다음과 같습니다.

• 길이가 1인 구간은 원소 하나만 제거하면 되므로 dp[i][i] = 1입니다.
• 일반적인 경우, 첫 번째 원소를 따로 제거하는 경우를 기본값으로 둡니다: dp[i][j] = 1 + dp[i+1][j].
• 인접한 두 원소가 같다면(arr[i] == arr[i+1]), 두 원소를 한 번에 제거할 수 있습니다: dp[i][j] = min(dp[i][j], 1 + dp[i+2][j]).
• 구간 안에서 arr[i] == arr[k]인 k가 존재하면, 양 끝 원소를 마지막에 함께 제거되는 회문의 일부로 묶어 처리할 수 있습니다: dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k+1][j]).

모든 구간에 대해 위 규칙을 적용한 뒤, 최종적으로 dp[0][n-1]이 곧 정답이 됩니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int minimumMoves(vector<int>& arr) {
        int n = arr.size();
        vector<vector<int> > dp(n + 1, vector<int>(n + 1));
        for (int l = 1; l <= n; l++) {
            for (int i = 0, j = l - 1; j < n; i++, j++) {
                if (l == 1) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = 1 + dp[i + 1][j];
                    if (i + 1 < n && arr[i] == arr[i + 1])
                    dp[i][j] = min(dp[i][j], 1 + dp[i + 2][j]);
                    for (int k = i + 2; k <= j; k++) {
                        if (arr[i] == arr[k]) {
                           dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j]);
                        }
                   }
               }
           }
       }
        return dp[0][n - 1];
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2};
    cout << (ob.minimumMoves(v));
}

실행 결과

입력

[1,2]

출력

2

배열 [1, 2]에는 회문이 될 수 있는 길이 2 이상의 연속 구간이 없으므로, 각 원소를 한 번씩 제거해야 합니다. 따라서 총 2번의 이동이 필요하며, 위 코드는 이를 정확히 계산해냅니다.