Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀기: 배열의 합을 목표 값에 가장 가깝게 만드는 최적의 값 찾기

정수 배열 arr와 목표 값 target이 주어졌다고 가정해 보겠습니다. 이때 배열에서 특정 정수 value보다 큰 모든 요소를 value로 변경한 뒤, 변경된 배열의 합이 목표 값에 최대한 가까워지도록 하는 정수를 찾아야 합니다. 후보 값이 여러 개일 경우에는 그중 가장 작은 값을 반환합니다.

예를 들어 배열이 [4, 9, 3]이고 목표 값이 10이라면 정답은 3입니다. 3을 선택하면 배열이 [3, 3, 3]이 되어 합이 9가 되고, 이는 10에 가장 근접한 결과입니다.

문제 해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

  • n := 배열의 크기, avg := target / n으로 설정하고, sum := 0, cnt := 0으로 초기화합니다.
  • i를 0부터 n−1까지 반복하면서 다음을 수행합니다.
    • 만약 arr[i] <= avg라면, sum에 arr[i]를 더하고 cnt를 1 증가시킵니다.
  • target − sum == 0이라면 avg를 반환합니다.
  • high := (target − sum) / (n − cnt)의 올림 값
  • low := (target − sum) / (n − cnt)의 내림 값
  • lowDiff := |target − (low × (n − cnt) + sum)|
  • highDiff := |target − (high × (n − cnt) + sum)|
  • lowDiff <= highDiff이면 low를 반환하고, 그렇지 않으면 high를 반환합니다.

아래 구현 예시를 통해 더 자세히 살펴보겠습니다.

C++ 구현 예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int findBestValue(vector<int>& arr, int target) {
      int n = arr.size();
      int avg = target / n;
      int sum = 0;
      int cnt = 0;
      for(int i = 0; i < n; i++){
         if(arr[i] <= avg){
            sum += arr[i];
            cnt++;
         }
      }
      if(target - sum == 0)return avg;
      int high = ceil(((target - sum) * 1.0)/ ((n - cnt) * 1.0));
      int low = floor(((target - sum) * 1.0) / ((n - cnt) * 1.0));
      int lowDiff = abs(target - (low * (n - cnt) + sum));
      int highDiff = abs(target - (high * (n - cnt) + sum));
      if( lowDiff <= highDiff)return low;
      return high;
   }
};
main(){
   vector<int> v = {4,9,3,2};
   Solution ob;
   cout << (ob.findBestValue(v, 10));
}

입력

[4,9,3,2]
10

출력

3