N개의 요소가 있는 배열이 있다고 가정합니다. 주어진 작업에 따라 배열에서 요소를 제거해야 합니다. 작업은 배열의 두 숫자를 선택하고 더 큰 숫자를 제거하는 것과 같습니다. 이 작업에 포함된 비용은 더 작은 숫자와 동일합니다. 이 작업을 기반으로 한 번에 하나의 요소만 삭제하고 최소 비용으로 작업을 수행해야 합니다. 배열에 {4, 2, 5}가 있다고 가정합니다. 4와 2를 선택하고 비용 2를 지불하여 4를 제거한 다음 비용 2로 5를 다시 제거합니다.
접근 방식은 너무 간단합니다. 비용이 더 작은 것과 같을 것이라는 것을 알고 있으므로 비용을 줄이기 위해 가장 작은 것을 취하고 다른 요소를 선택한 다음 더 큰 것을 제거하면 비용은 항상 더 작은 것입니다. 따라서 총 비용은 (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