C++로 회문 부분 리스트를 제거하는 최소 연산 횟수 구하기

문제 개요

숫자 배열 nums가 주어졌을 때, 회문(palindrome) 형태의 부분 리스트(sublist)를 한 번의 연산으로 삭제할 수 있다고 가정해 봅시다. 이때 배열 전체를 비우기 위해 필요한 최소 연산 횟수를 구하는 것이 목표입니다.

예를 들어 입력이 nums = [6, 2, 4, 4, 2, 10, 6]이라면 정답은 2입니다. 먼저 가운데의 부분 리스트 [2, 4, 4, 2]를 제거하면 [6, 10, 6]이 남습니다. 이 배열 역시 회문이므로 한 번 더 제거하면 배열이 완전히 비워집니다.

접근 방식: 구간 DP와 메모이제이션

이 문제는 구간 단위 동적 계획법과 메모이제이션을 결합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 구간 [i, j]에 대해 "이 구간을 모두 제거하는 데 필요한 최소 연산 횟수"를 재귀적으로 계산하고, 그 결과를 dp 테이블에 캐싱하여 중복 계산을 방지하는 것입니다.

알고리즘 단계

dfs(i, j, v)는 구간 [i, j]를 제거하는 데 필요한 최소 연산 횟수를 반환하는 함수입니다. 다음 순서로 로직을 구성합니다.

크기 105 × 105의 2차원 배열 dp를 선언합니다.
시작 인덱스 i, 끝 인덱스 j와 배열 v를 매개변수로 받는 dfs() 함수를 정의합니다.
기저 사례 1: i > j이면 제거할 요소가 없으므로 0을 반환합니다.
기저 사례 2: i == j이면 요소 하나는 항상 회문이므로 1을 반환합니다.
기저 사례 3: j - i == 1이면 두 요소가 같으면 1, 다르면 2를 반환합니다.
v[i] == v[i + 1]이면 인접한 두 요소를 한 번에 제거할 수 있으므로 ret := 1 + dfs(i + 2, j, v)로 갱신합니다.
dp[i][j] != -1이면 이미 계산된 결과가 있으므로 그 값을 그대로 반환합니다(메모이제이션).
첫 번째 또는 마지막 요소 하나만 따로 제거하는 경우를 고려하여 ret := min(ret, 1 + min(dfs(i + 1, j, v), dfs(i, j - 1, v)))로 갱신합니다.
v[i] == v[j]이면 양쪽 끝을 하나의 회문으로 함께 제거할 수 있으므로 ret := min(ret, dfs(i + 1, j - 1, v))로 갱신합니다.
k를 i + 2부터 j - 1까지 순회하면서 v[i] == v[k]인 지점을 발견하면, 구간 [i, k]를 하나의 회문 묶음으로 처리한다고 보고 ret := min(ret, dfs(i + 1, k - 1, v) + dfs(k + 1, j, v))로 갱신합니다.
마지막으로 dp[i][j] = ret을 저장한 뒤 반환합니다.

메인 함수의 처리 과정

memset을 사용해 dp 배열 전체를 -1로 초기화합니다.
n := nums의 크기를 구합니다.
dfs(0, n - 1, nums)의 결과값을 반환합니다.

C++ 구현 예제

다음 구현을 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int dp[105][105];
int dfs(int i,int j, vector <int>& v){
    int ret= INT_MAX;
    if(i > j)
       return 0;
    if(i == j)
       return 1;
    if(j - i == 1){
       return v[i] == v[j] ? 1 : 2;
    }
    if(i + 1 <= j && v[i] == v[i + 1]){
       ret = 1 + dfs(i + 2, j, v);
    }
    if(dp[i][j] != -1) return dp[i][j];
       ret = min({ret, 1 + min(dfs(i + 1, j, v), dfs(i, j - 1, v))});
    if(v[i] == v[j]){
       ret = min(ret, dfs(i + 1, j - 1, v));
    }
    for(int k = i + 2; k < j; k++){
       if(v[i] == v[k]){
          ret = min(ret, dfs(i + 1, k - 1, v) + dfs(k + 1, j, v));
       }
    }
    return dp[i][j] = ret;
}
int solve(vector<int>& nums) {
    memset(dp , -1, sizeof dp);
    int n = nums.size();
    return dfs(0, n - 1, nums);
}
int main(){
    vector<int> v = {6, 2, 4, 4, 2, 10, 6};
    cout << solve(v);
}

입력 및 출력

입력:

{6, 2, 4, 4, 2, 10, 6}

출력:

복잡도 분석 및 마무리

이 풀이의 상태 개수는 구간의 개수만큼 O(n²)이며, 각 상태에서 분할 지점 k를 탐색하는 데 최대 O(n)이 걸리므로 전체 시간 복잡도는 약 O(n³), 공간 복잡도는 O(n²)입니다. 회문을 단위로 구간을 나누어 제거하는 이 패턴은 구간 DP 문제에서 자주 등장하는 유형이므로, 기저 사례 처리와 세 가지 분기(인접 쌍 제거, 양끝 제거, 내부 매칭)를 확실히 익혀두면 다양한 변형 문제에도 큰 도움이 됩니다.