C++로 d일 동안 첫 번째 건초 더미의 최대 개수 계산하기

n개의 요소를 가진 배열 A와 정수 d가 주어졌다고 가정해 봅시다. 한 농부가 농장에 n개의 건초 더미를 배치했으며, i번째 더미에는 A[i]개의 건초가 들어 있습니다.

매일 소는 어떤 더미에서 인접한 더미로 건초 하나를 옮길 수 있습니다. 물론 하루에 아무 작업도 하지 않을 수도 있습니다. 소의 목표는 d일 안에 첫 번째 더미의 건초 수를 최대한 많이 만드는 것이며, 우리는 d일 후 첫 번째 더미에 존재할 수 있는 최대 건초 개수를 계산해야 합니다.

예를 들어 입력이 d = 5, A = [1, 0, 3, 2]라고 해봅시다. 이 경우 출력은 3이 됩니다. 첫째 날과 둘째 날에는 3번째 더미(인덱스 2)에서 2번째 더미(인덱스 1)로 건초를 하나씩 옮기고, 그다음 이틀 동안 2번째 더미에서 첫 번째 더미로 옮기면 되기 때문입니다.

문제 해결 접근 방식

이 문제는 그리디(Greedy) 알고리즘으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

i번째 더미에서 첫 번째 더미까지 건초 하나를 옮기려면 정확히 i번의 이동(즉, i일)이 필요합니다.
따라서 첫 번째 더미에 가까운 더미부터 순서대로 확인하면서, 남은 일수 d로 옮길 수 있는 최대한의 건초를 가져옵니다.

구체적인 단계는 다음과 같습니다.

a0 := A[0]
n := size of A
for initialize i := 1, when i < n, update (increase i by 1), do:
   ai := A[i]
   w := minimum of ai and d / i
   a0 := a0 + w
   d := d - w * i
return a0

C++ 구현 예제

더 나은 이해를 돕기 위해 전체 구현 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int solve(int d, vector<int> A){
   int a0 = A[0];
   int n = A.size();
   for (int i = 1; i < n; i++){
      int ai = A[i];
      int w = min(ai, d / i);
      a0 += w;
      d -= w * i;
   }
   return a0;
}
int main(){
   int d = 5;
   vector<int> A = { 1, 0, 3, 2 };
   cout << solve(d, A) << endl;
}

입력

5, { 1, 0, 3, 2 }

출력

동작 원리 설명

위 예제에서 알고리즘이 어떻게 동작하는지 단계별로 살펴보겠습니다.

초기 상태: a0 = 1, d = 5
i = 1일 때: A[1] = 0이므로 옮길 건초가 없습니다. (w = min(0, 5/1) = 0)
i = 2일 때: A[2] = 3이지만, 각 건초당 2일이 필요하므로 최대 5/2 = 2개만 옮길 수 있습니다. a0 = 3, d = 5 - 4 = 1
i = 3일 때: 남은 일수가 1일뿐이라 3일이 필요한 건초는 옮길 수 없습니다. (w = min(2, 1/3) = 0)

최종적으로 첫 번째 더미에는 3개의 건초가 쌓이게 됩니다. 이 알고리즘의 시간 복잡도는 O(n)으로 매우 효율적입니다.