C++ 배열 원소 제거 비용 최소화하기

배열에 N개의 원소가 있다고 가정해 보겠습니다. 주어진 연산 규칙에 따라 배열에서 원소를 제거해야 합니다. 연산 방식은 다음과 같습니다. 배열에서 임의의 두 숫자를 선택한 뒤, 그중 더 큰 수를 제거하고, 이때 발생하는 비용은 두 수 중 작은 값과 같습니다. 한 번에 하나의 원소만 제거할 수 있으며, 전체 작업을 최소 비용으로 완료하는 것이 목표입니다.

예를 들어 배열이 {4, 2, 5}라고 해보겠습니다. 먼저 4와 2를 선택해 4를 제거하면 비용 2가 발생하고, 이어서 2와 5를 선택해 5를 제거하는 데 역시 비용 2가 듭니다. 따라서 총 비용은 4가 됩니다.

핵심 아이디어

접근 방법은 매우 간단합니다. 비용은 항상 두 수 중 작은 값과 같으므로, 비용을 최소화하려면 배열의 최솟값을 계속 파트너로 선택하면 됩니다. 즉, 최솟값과 다른 원소를 짝지어 더 큰 값을 제거하면, 모든 연산의 비용이 항상 최솟값으로 고정됩니다.

N개의 원소 중 하나만 남기면 되므로 총 N – 1번의 연산이 필요하고, 각 연산의 비용이 최솟값이므로 전체 최소 비용은 다음과 같습니다.

총 비용 = (N – 1) × 최솟값

예제 코드

#include <iostream>
#include <algorithm>
using namespace std;
int getMinimumCost(int arr[], int n) {
   int smallest = *min_element(arr, arr+n);
   return smallest * (n - 1);
}
int main() {
   int arr[] = { 4, 2, 5 };
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Minimum cost: " << getMinimumCost(arr, n);
}

실행 결과

Minimum cost: 4

코드 설명

min_element 함수를 사용해 배열 전체를 한 번 순회하며 최솟값을 찾은 뒤, 여기에 (N – 1)을 곱해 결과를 반환합니다. 시간 복잡도는 O(N), 공간 복잡도는 O(1)로 매우 효율적이며, 배열의 크기가 커져도 성능 저하 없이 빠르게 답을 계산할 수 있습니다.