문제 개요
이 문제에서는 n개의 숫자로 이루어진 배열과 하나의 정수 값 k가 주어집니다. 우리의 목표는 주어진 삭제 규칙을 적용했을 때 배열이 가질 수 있는 최소 크기를 구하는 것입니다.
문제 설명
배열에 포함된 원소의 개수를 최대한 줄여야 합니다. 사용할 수 있는 삭제 연산은 한 번에 3개의 원소를 제거하는 것이며, 이 연산은 다음 두 가지 조건을 모두 만족할 때만 수행할 수 있습니다.
- 조건 1 — 세 원소는 서로 인접해 있어야 합니다.
- 조건 2 — 인접한 두 원소 사이의 차이가 k여야 합니다. 즉, arr[i + 1] = arr[i] + k 이고 arr[i + 2] = arr[i + 1] + k 를 만족해야 합니다.
입력 예시
{4, 6, 8, 4, 1, 5 }, k = 2출력 결과
3
설명
인덱스 0, 1, 2에 해당하는 원소(4, 6, 8)가 두 조건을 모두 충족하므로, 한 번의 삭제 연산을 수행할 수 있습니다. 그 결과 남는 원소는 3개입니다.
풀이 접근 방법
이 문제는 다소 까다롭습니다. 삭제 연산을 한 번 수행한 이후에야 새로운 삭제 기회가 생길 수 있기 때문입니다. 예를 들어, 원소 5, 6, 7을 먼저 삭제하면 그 결과로 만들어진 새 배열에서 원소 3, 4, 5가 이제 삭제 조건을 만족하게 될 수 있습니다.
이처럼 중복되는 부분 문제(overlapping subproblems)가 존재하는 유형은 동적 계획법(Dynamic Programming)으로 해결하는 것이 적합합니다. DP[] 행렬을 유지하여 부분 문제의 결과를 저장해 두고, 필요할 때 다시 계산하지 않고 재사용하는 메모이제이션(memoization) 기법을 활용합니다.
구현 예시 코드
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
int DP[MAX][MAX];
int calcMinSize(int arr[], int start, int end, int k){
if (DP[start][end] != -1)
return DP[start][end];
if ( (end-start + 1) < 3)
return end-start +1;
int minSize = 1 + calcMinSize(arr, start+1, end, k);
for (int i = start+1; i<=end-1; i++){
for (int j = i+1; j <= end; j++ ){
if (arr[i] == (arr[start] + k) && arr[j] == (arr[start] +
2*k) && calcMinSize(arr, start+1, i-1, k) == 0 && calcMinSize(arr, i+1, j- 1, k) == 0) {
minSize = min(minSize, calcMinSize(arr, j+1, end, k));
}
}
}
return (DP[start][end] = minSize);
}
int main() {
int arr[] = {4, 6, 8, 4, 1, 5 };
int n = sizeof(arr)/sizeof(arr[0]);
int k = 2;
memset(DP, -1, sizeof(DP));
cout<<"The minimum possible size of the array after removal is "<<calcMinSize(arr, 0, n-1, k);
return 0;
}실행 결과
The minimum possible size of the array after removal is 3
정리
이 알고리즘은 재귀적으로 모든 가능한 세 원소 조합을 검사하면서, 각 구간(start ~ end)에 대한 최소 크기를 DP 테이블에 캐싱합니다. 덕분에 동일한 부분 문제를 반복해서 계산하는 낭비를 없애고 전체 탐색 시간을 크게 줄일 수 있습니다.