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

C++로 풀기: 액세스할 때마다 최댓값이 1씩 감소하는 배열의 최댓값 합 구하기

이 문제에서는 N개의 정수로 이루어진 배열 arr[]과 정수 m이 주어지며, 배열의 최댓값에 접근할 때마다 해당 값이 1씩 감소한다는 조건 하에 최댓값들의 합을 구하는 프로그램을 작성해야 합니다.

문제 설명

배열에서 최댓값을 하나씩 꺼내 합계에 더하고, 꺼낸 값은 1만큼 감소시켜 다시 배열에 넣는 작업을 총 m번 반복했을 때 얻을 수 있는 최댓값들의 합(maxSum)을 구하는 것이 목표입니다.

예제로 이해하기

입력

arr[] = {3, 6, 7, 8, 8}, m = 3

출력

23

풀이 과정

1번째 반복: 갱신 전 배열 = {3, 6, 7, 8, 8}, 최댓값 = 8, 합 = 8, 갱신 후 배열 = {3, 6, 7, 7, 8}
2번째 반복: 갱신 전 배열 = {3, 6, 7, 7, 8}, 최댓값 = 8, 합 = 8 + 8 = 16, 갱신 후 배열 = {3, 6, 7, 7, 7}
3번째 반복: 갱신 전 배열 = {3, 6, 7, 7, 7}, 최댓값 = 7, 합 = 16 + 7 = 23, 갱신 후 배열 = {3, 6, 6, 7, 7}
최종 합 = 23

해결 접근 방법

핵심 아이디어는 매번 배열의 최댓값을 찾아 maxSum에 더한 뒤, 그 값을 1 감소시켜 다시 저장하는 것입니다. 이 과정을 m번 반복하면 답을 구할 수 있습니다.

배열의 최댓값을 빠르게 찾는 가장 효율적인 방법은 최대 힙(max heap) 자료구조를 활용하는 것입니다. 배열의 모든 원소를 최대 힙에 삽입하면 힙의 루트에 항상 최댓값이 위치하므로, 루트 값을 꺼내 maxSum에 더한 후 1을 뺀 값을 다시 힙에 삽입하면 됩니다. 이 작업을 m번 반복하면 원하는 maxSum을 얻을 수 있습니다.

알고리즘

  1. 초기화: maxSum = 0으로 설정합니다.
  2. 1단계: 최대 힙을 생성하고 배열의 모든 원소를 삽입합니다.
  3. 2단계: i가 0부터 m까지 순회하며 3~5단계를 반복합니다.
  4. 3단계: 힙의 루트 원소를 maxVal에 저장한 뒤 pop합니다.
  5. 4단계: maxVal을 maxSum에 더합니다. (maxSum += maxVal)
  6. 5단계: 1 감소시킨 maxVal을 다시 최대 힙에 삽입합니다.
  7. 6단계: maxSum을 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

long calcMaxSumDec(int arr[], int m, int n) {
    long maxSum = 0;
    long maxVal;
    priority_queue<long> max_heap;
    for (int i = 0; i < n; i++) {
        max_heap.push(arr[i]);
    }
    for (int i = 0; i < m; i++) {
        maxVal = max_heap.top();
        maxSum += maxVal;
        max_heap.pop();
        max_heap.push(maxVal - 1);
    }
    return maxSum;
}

int main() {
    int arr[] = { 2, 3, 5, 4 }, m = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximums from array when the maximum decrements after every access is "
         << calcMaxSumDec(arr, m, n);
}

실행 결과

The maximums from array when the maximum decrements after every access is 13

위 예제에서 배열 {2, 3, 5, 4}의 최댓값은 5입니다. 첫 번째 접근에서 5를 더하고 4로 감소시키면, 두 번째와 세 번째 접근에서는 4를 두 번 더하게 되어 최종 합은 5 + 4 + 4 = 13이 됩니다.

시간 및 공간 복잡도

힙 초기화에 O(N log N)이 소요되고, 각 접근마다 pop과 push 연산에 O(log N)이 걸리므로 전체 시간 복잡도는 O((N + m) log N)입니다. 공간 복잡도는 힙 저장을 위해 O(N)입니다. 참고로 배열을 내림차순으로 한 번 정렬한 뒤 순서대로 값을 꺼내는 방식(O(N log N))으로도 동일한 결과를 얻을 수 있지만, 원소 개수가 많고 m이 작은 경우에는 최대 힙을 사용하는 편이 더 유리합니다.