C++로 구현하는 배열 최댓값 합 구하기: 접근할 때마다 최댓값이 1씩 감소하는 경우

이 문제에서는 배열 arr[]와 정수 M이 주어집니다. 우리가 만들어야 할 프로그램은 C++에서 배열에 접근할 때마다 최댓값이 1씩 감소한다는 조건 아래, M번의 접근 동안 얻은 최댓값들의 합을 구하는 것입니다.

문제 설명

최댓값을 찾기 위해 배열에서 가장 큰 원소를 선택하고, 값을 꺼낼 때마다 해당 원소를 1씩 감소시키는 작업을 총 M번 반복합니다. 그리고 각 접근에서 얻은 최댓값을 모두 더한 합계를 결과로 출력합니다.

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

입력: arr[] = {3, 6, 8, 9}, M = 2

출력: 17

해설

1회차: 최댓값 = 9, 합계 = 9, 갱신된 배열 = {3, 6, 8, 8}

2회차: 최댓값 = 8, 합계 = 9 + 8 = 17, 갱신된 배열 = {3, 6, 7, 8}

즉, 첫 번째 접근에서 배열의 최댓값인 9를 얻고 이 값을 8로 줄입니다. 두 번째 접근에서는 현재 최댓값인 8을 얻고 다시 7로 줄입니다. 두 번의 접근으로 얻은 값의 합은 9 + 8 = 17이 됩니다.

해결 방법

가장 효율적인 해결 방법은 최대 힙(max heap)을 사용하는 것입니다. 최대 힙은 항상 루트(최상단)에 최댓값이 위치하는 자료구조이므로, 매번 배열 전체를 탐색하지 않고도 O(log N) 시간 안에 최댓값을 찾을 수 있습니다.

알고리즘의 진행 순서는 다음과 같습니다.

1. 배열의 모든 원소를 최대 힙에 삽입합니다.
2. M번 반복하면서 힙의 루트(현재 최댓값)를 꺼내어(pop) 합계 변수에 더합니다.
3. 꺼낸 값에서 1을 뺀 후 다시 힙에 삽입(push)합니다.
4. M번의 반복이 끝나면 누적된 합계를 반환합니다.

이 방법의 시간 복잡도는 O(N + M log N)입니다. 여기서 N은 배열의 크기, M은 접근 횟수를 의미합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int getSum(int arr[], int N, int M) {
   int sumVal = 0;
   priority_queue<int> heap;
   for (int i = 0; i < N; i++)
      heap.push(arr[i]);
   while (M--) {
      int maximumVal = heap.top();
      sumVal += maximumVal;
      heap.pop();
      heap.push(maximumVal - 1);
   }
   return sumVal;
}
int main() {
   int arr[] = { 3, 6, 8, 9};
   int M = 2;
   int N = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum from array when the maximum decrements after every access is "<<getSum(arr, N,M);
}

실행 결과

The maximum from array when the maximum decrements after every access is 17

C++ STL의 priority_queue는 기본적으로 최대 힙으로 동작하므로, 위 코드처럼 top()으로 최댓값에 바로 접근할 수 있습니다. 이처럼 우선순위 큐를 활용하면 반복적인 최댓값 조회와 갱신 작업을 간결하고 효율적으로 처리할 수 있습니다.