C++에서 길을 건너는 데 필요한 최소 초기 에너지

양수와 음수가 저장되는 배열이 있다고 가정합니다. 배열은 거리의 한쪽 끝에서 다른 쪽 끝까지의 체크포인트를 나타냅니다. 양수 및 음수 값은 체크포인트의 에너지를 나타냅니다. 양수 값은 에너지를 증가시킬 수 있고 음수 값은 에너지를 감소시킵니다. 에너지 준위가 0 또는 0 미만이 되지 않도록 길을 건너기 위한 초기 에너지 준위를 찾아야 합니다.

배열 A ={4, -6, 2, 3}이 있다고 가정합니다. 초기 에너지를 0으로 둡니다. 따라서 첫 번째 체크포인트에 도달한 후 에너지는 4입니다. 이제 두 번째 체크포인트로 이동하려면 에너지는 4 + (-6) =-2가 됩니다. 따라서 에너지는 0보다 작습니다. 따라서 3으로 여행을 시작해야 합니다. 따라서 첫 번째 체크포인트 이후에는 3 + 4 =7이 되고 두 번째 체크포인트로 이동한 후에는 7 + (-6) =1이 됩니다.

알고리즘

minInitEnergy(arr, n):
begin
   initEnergy := 0
   currEnergy := 0
   flag := false
   for i in range 0 to n, do
      currEnergy := currEnergy + arr[i]
      if currEnergy <= 0, then
         initEnergy := initEnergy + absolute value of currEnergy + 1
         currEnergy := 1
         flag := true
      end if
   done
   if flag is false, return 1, otherwise return initEnergy
end

예시

#include <iostream>
#include <cmath>
using namespace std;
int minInitEnergy(int arr[], int n){
   int initEnergy = 0;
   int currEnergy = 0;
   bool flag = false;
   for (int i = 0; i<n; i++){
      currEnergy = currEnergy + arr[i];
      if (currEnergy <= 0){
         initEnergy = initEnergy + abs(currEnergy) + 1;
         currEnergy = 1;
         flag = true;
      }
   }
   if (flag == false)
      return 1;
   else
      return initEnergy;
}
int main() {
   int A[] = {4, -6, 2, 3};
   int n = sizeof(A)/sizeof(A[0]);
   cout << "Minimum Energy: " << minInitEnergy(A, n);
}

출력

Minimum Energy: 3