C++로 구하는 최대 무게 차이(Maximum Weight Difference)

이 문제에서는 배열 arr[]과 숫자 M이 주어지며, 우리의 과제는 C++ 프로그램을 작성하여 최대 무게 차이(Maximum Weight Difference)를 계산하는 것입니다.

문제 설명

배열에서 M개의 원소를 선택했을 때, 선택한 원소들의 합과 나머지 원소들의 합 사이의 절대 차이가 최대가 되도록 하는 값을 찾아야 합니다.

예시를 통해 문제를 이해해 보겠습니다.

입력: arr[] = {3, 1, 6, 9, 4}, M = 3

출력: 15

설명

4, 6, 9를 선택하면 그 합은 19가 됩니다. 나머지 숫자들(3, 1)의 합은 4이므로, 두 합의 절대 차이는 다음과 같습니다.

|19 − 4| = 15

해결 접근 방법

이 문제의 핵심은 최대 차이가 오직 'M개의 가장 큰 수' 또는 'M개의 가장 작은 수'를 선택하는 경우에만 가능하다는 사실에 있습니다. 따라서 두 가지 경우를 모두 계산하고, 각각의 절대 차이를 비교하여 더 큰 값을 최종 결과로 반환해야 합니다.

M개의 가장 큰 수와 가장 작은 수를 손쉽게 찾기 위해 먼저 배열을 정렬한 뒤, 정렬된 배열에서 앞쪽 M개(최솟값들)와 뒤쪽 M개(최댓값들)의 합을 구해 계산하면 됩니다.

C++ 예시 코드

#include <bits/stdc++.h>
using namespace std;
int maxWeightDifference(int arr[], int N, int M){
    int maxabsDiff = -1000;
    sort(arr, arr + N);
    int sumMin = 0, sumMax = 0, arrSum = 0;
    for(int i = 0; i < N; i++){
        arrSum += arr[i];
        if(i < M)
            sumMin += arr[i];
        if(i >= (N-M))
            sumMax += arr[i];
    }
    maxabsDiff = max(abs(sumMax - (arrSum - sumMax)), abs(sumMin -(arrSum - sumMin)));
    return maxabsDiff;
}
int main(){
    int arr[] = {3, 1, 6, 9, 4} ;
    int M = 3;
    int N = sizeof(arr)/sizeof(arr[0]);
    cout<<"The maximum weight difference is "<<maxWeightDifference(arr,N, M);
    return 0;
}

실행 결과

The maximum weight difference is 15