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

문제 개요

양수와 음수가 저장된 배열이 있다고 가정해 봅시다. 이 배열은 거리의 한쪽 끝에서 반대쪽 끝까지 이어지는 체크포인트를 나타내며, 각 값은 해당 지점에서 변화하는 에너지의 양을 의미합니다. 양수는 에너지를 증가시키고, 음수는 에너지를 감소시킵니다. 우리의 목표는 이동 과정 전체에서 에너지 수준이 단 한 번도 0이 되거나 0 미만으로 떨어지지 않도록 하는 최소 초기 에너지 값을 구하는 것입니다.

예를 들어 배열 A = {4, -6, 2, 3}이 있고 초기 에너지가 0이라고 가정해 보겠습니다. 첫 번째 체크포인트에 도착하면 에너지는 4가 됩니다. 하지만 두 번째 체크포인트로 이동하는 시점에 에너지는 4 + (-6) = -2가 되어 조건을 위반하게 됩니다. 따라서 초기 에너지를 3으로 설정하고 출발해야 합니다. 그러면 첫 번째 체크포인트 이후에는 3 + 4 = 7이 되고, 두 번째 체크포인트에 도착했을 때도 7 + (-6) = 1로 항상 양수를 유지할 수 있습니다.

알고리즘

핵심 아이디어는 간단합니다. 배열을 왼쪽부터 순회하면서 누적 에너지를 계산하고, 누적 에너지가 0 이하로 떨어지는 순간 부족한 만큼(절댓값 + 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

C++ 구현 예제

#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

코드 설명 및 복잡도

initEnergy는 최종적으로 반환될 최소 초기 에너지를 저장하고, currEnergy는 현재까지의 누적 에너지를 추적합니다. 순회 도중 currEnergy가 0 이하가 되면, 부족분의 절댓값에 1을 더한 값을 initEnergy에 누적한 뒤 currEnergy를 1로 재설정하여 이후 계산이 올바른 기준 위에서 진행되도록 합니다. 만약 한 번도 에너지가 0 이하로 떨어지지 않았다면(flag == false), 초기 에너지 1만으로 충분하므로 1을 반환합니다.

배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가로 사용하는 메모리는 상수 공간으로 O(1)입니다.