k를 초과하지 않는 사탕 추가 연산의 최대 횟수를 계산하는 C++ 코드

문제 개요

n개의 요소를 가진 배열 A와 하나의 숫자 k가 주어집니다. 사탕 더미가 총 n개 있으며, i번째 더미에는 A[i]개의 사탕이 들어 있습니다. 우리는 서로 다른 두 인덱스 i와 j(i ≠ j)를 골라 A[j]에 A[i]개의 사탕을 추가하는 연산을 수행할 수 있으며, 이때 원본인 A[i]는 줄어들지 않습니다.

이 연산은 원하는 만큼 반복할 수 있지만 한 가지 제약이 있습니다. 어떤 더미라도 k개보다 엄격하게 많은 사탕을 담게 되면 더 이상 연산을 진행할 수 없습니다. 목표는 이 조건을 지키면서 연산을 수행할 수 있는 최대 횟수를 구하는 것입니다.

예시

입력이 A = [1, 2, 3], k = 5라고 가정해 보겠습니다. 이때 출력은 5가 됩니다. i = 0(A[0] = 1)을 소스로 삼아, j = 1인 더미에는 3번((5 − 2) ÷ 1), j = 2인 더미에는 2번((5 − 3) ÷ 1) 사탕을 추가할 수 있기 때문입니다. 합계는 총 5번입니다.

풀이 접근 방법

이 문제는 그리디(greedy) 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1. 배열 A를 오름차순으로 정렬합니다.
2. 한 번의 연산으로 추가되는 사탕 수가 적을수록 더 많은 연산을 수행할 수 있으므로, 항상 가장 작은 값 A[0]을 소스로 사용합니다.
3. 정렬 후 각 더미 i(1 ≤ i ≤ n−1)에 대해서는 (k − A[i]) ÷ A[0]번의 연산을 안전하게 수행할 수 있으며, 이 과정에서 어떤 더미도 k를 초과하지 않습니다.
4. 모든 더미에 대해 계산한 값을 모두 더하면 정답이 됩니다.

의사 코드

ans := 0
n := 배열 A의 크기
배열 A를 오름차순으로 정렬
for i := 1 부터 i < n 까지 1씩 증가하며 반복:
    ans := ans + (k - A[i]) / A[0]
return ans

C++ 구현 예제

아래 구현을 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int k){
    int ans = 0;
    int n = A.size();
    sort(A.begin(), A.end());
    for (int i = 1; i < n; i++){
        ans += (k - A[i]) / A[0];
    }
    return ans;
}
int main(){
    vector<int> A = { 1, 2, 3 };
    int k = 5;
    cout << solve(A, k) << endl;
}

입력

{ 1, 2, 3 }, 5

출력

5

복잡도 분석

배열 정렬에 O(n log n)의 시간이 소요되고, 이후의 단일 반복문은 O(n)이므로 전체 시간 복잡도는 O(n log n)입니다. 추가로 사용되는 메모리가 상수 수준이므로 공간 복잡도는 O(1)입니다.