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

C++ 알고리즘: 최대 k번 증가시켜 같은 값으로 만들 수 있는 배열 요소의 최대 개수 구하기

이 문제의 목표는 주어진 배열에서 각 요소를 최대 k번까지 증가시킬 수 있을 때, 동일한 값으로 만들 수 있는 요소의 최대 개수를 구하는 것입니다.

구체적인 예시를 통해 문제를 살펴보겠습니다.

입력 예제 1

a[] = {1, 3, 8}, k = 4

출력

2

설명

배열의 1을 세 번 증가시키고 3을 한 번 증가시키면 총 4번의 업데이트(k = 4) 안에서 두 개의 4를 만들 수 있습니다. 결과적으로 배열은 {4, 4, 8}이 되며, 같은 값으로 만든 요소의 개수는 2개입니다.

입력 예제 2

arr = {2, 5, 9}, k = 2

출력

0

요소 간의 차이가 너무 커서 k = 2번의 증가만으로는 어떤 두 요소도 같은 값으로 만들 수 없으므로 결과는 0입니다.

접근 방법

이 문제는 접두사 합(Prefix Sum)과 이진 탐색(Binary Search)을 활용하여 효율적으로 해결할 수 있습니다. 프로그램의 동작 흐름은 다음과 같습니다.

  • main() 함수에서 배열 요소를 저장할 int a[], 배열의 크기를 저장할 size, 가능한 최대 업데이트 횟수를 저장할 k를 초기화합니다.

  • Max() 함수에서는 먼저 배열을 오름차순으로 정렬한 뒤, 접두사 합을 저장할 p[size + 1]과 해당 위치까지의 최대값을 저장할 m[size + 1] 두 개의 보조 배열을 선언합니다.

  • i = 0부터 i <= size까지 반복하면서 p[i] = 0, m[i] = 0으로 초기화합니다.

  • 루프가 끝난 후 m[0] = arr[0], p[0] = arr[0]으로 설정합니다.

  • i = 1부터 i < size까지 반복하면서 p[i] = p[i - 1] + arr[i]로 접두사 합을 계산하고, m[i] = max(m[i - 1], arr[i])로 해당 위치까지의 최대값을 계산합니다.

  • 루프 종료 후 왼쪽 경계 Lt = 1, 오른쪽 경계 Rt = size, 최종 답을 저장할 result를 초기화한 뒤 이진 탐색을 시작합니다.

  • 조건 (Lt < Rt)로 while 루프를 실행합니다. 루프 안에서 mid = (Lt + Rt) / 2를 계산하고, EleCal(p, m, mid - 1, k, size)가 참이면 result = mid, Lt = mid + 1로 설정합니다.

  • 그렇지 않으면 Rt = mid - 1로 설정합니다.

  • 루프가 끝나면 result를 출력합니다.

  • bool EleCal() 함수에서는 for (int i = 0, j = x; j <= size; j++, i++) 조건으로 for 루프를 실행합니다.

  • 루프 안에서 x * m[j] - (p[j] - p[i]) <= k 조건을 검사하여 참이면 true를 반환합니다. 모든 경우를 확인한 후에도 만족하지 않으면 false를 반환합니다.

여기서 핵심 아이디어는 다음과 같습니다. 길이가 x인 연속 구간을 선택했을 때, 해당 구간의 모든 요소를 구간 내 최대값으로 맞추는 데 필요한 총 증가 횟수는 x * 최대값 - 구간 합입니다. 이 값이 k 이하라면 x개의 요소를 같은 값으로 만들 수 있습니다.

예제 코드

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

// x개의 요소를 같은 값으로 만들 수 있는지 확인하는 함수
bool EleCal(int p[], int m[], int x, int k, int size){
    for (int i = 0, j = x; j <= size; j++, i++){
        // x * 구간 최대값 - 구간 합이 k 이하인지 검사
        if (x * m[j] - (p[j] - p[i]) <= k)
            return true;
    }
    return false;
}

void Max(int arr[], int size, int k){
    // 배열을 오름차순으로 정렬
    sort(arr, arr + size);
    // 접두사 합을 저장할 배열
    int p[size + 1];
    // 최대값을 저장할 배열
    int m[size + 1];
    // 접두사 배열과 최대값 배열 초기화
    for (int i = 0; i <= size; ++i){
        p[i] = 0;
        m[i] = 0;
    }
    m[0] = arr[0];
    p[0] = arr[0];
    for (int i = 1; i < size; i++){
        // 배열의 접두사 합 계산
        p[i] = p[i - 1] + arr[i];
        // 해당 위치까지의 최대값 계산
        m[i] = max(m[i - 1], arr[i]);
    }
    // 이진 탐색
    int Lt = 1, Rt = size, result;
    while (Lt < Rt){
        int mid = (Lt + Rt) / 2;
        if (EleCal(p, m, mid - 1, k, size)){
            result = mid;
            Lt = mid + 1;
        }
        else
            Rt = mid - 1;
    }
    // 정답 출력
    cout<<result;
}

// 메인 함수
int main(){
    int a[] = { 1, 3, 8 };
    int size = sizeof(a) / sizeof(a[0]);
    int k = 4;
    Max(a, size, k);
    return 0;
}

실행 결과

2