N개의 요소로 이루어진 배열 A가 있다고 가정해 봅시다. 각 연산에서는 배열의 한 요소를 선택하여 1만큼 증가시키거나 1만큼 감소시킬 수 있습니다. 우리가 구해야 할 것은 다음 두 조건을 모두 만족하는 데 필요한 최소 연산 횟수입니다.
- 1부터 n까지의 모든 i에 대해, 첫 번째 항부터 i번째 항까지의 합(접두사 합)이 0이 아니어야 합니다.
- 1부터 n-1까지의 모든 i에 대해, 첫 번째 항부터 i번째 항까지의 합의 부호와 첫 번째 항부터 (i+1)번째 항까지의 합의 부호가 서로 반대여야 합니다.
예를 들어 입력 배열이 A = [1, -3, 1, 0]이라면 정답은 4가 됩니다. 총 네 번의 연산을 통해 수열을 1, -2, 2, -2 형태로 변형할 수 있으며, 이때 첫 번째~네 번째 항까지의 접두사 합은 각각 1, -1, 1, -1로 부호가 번갈아 나타나고 어느 것도 0이 아니기 때문입니다.
문제 해결 접근 방식
이 문제는 그리디(Greedy) 알고리즘을 활용하여 해결할 수 있습니다. 핵심 아이디어는 접두사 합이 양수로 시작하는 경우와 음수로 시작하는 경우, 이 두 가지 시나리오를 각각 시뮬레이션한 뒤 더 작은 연산 횟수를 선택하는 것입니다.
배열을 왼쪽에서 오른쪽으로 순회하면서, 현재 위치에서 기대하는 접두사 합의 부호(s)와 실제 계산된 새로운 누적합(nsum)을 비교합니다. 만약 nsum이 기대하는 부호와 맞지 않거나 0이라면, 해당 요소를 최소한으로 조정하여 조건을 만족시키고 그에 필요한 연산 횟수를 누적합니다.
알고리즘 단계
- 배열 A의 크기 n을 구합니다.
- 결과값 ret과 누적합 sum을 0으로 초기화합니다.
- 배열의 각 요소 ai에 대해 다음을 반복합니다.
- nsum = sum + ai를 계산합니다.
- s > 0일 때(접두사 합이 양수여야 하는 경우), nsum ≤ 0이라면 |nsum| + 1만큼의 연산을 ret에 더하고 ai를 그만큼 증가시켜 누적합이 1이 되도록 만듭니다.
- s ≤ 0일 때(접두사 합이 음수여야 하는 경우), nsum ≥ 0이라면 nsum + 1만큼의 연산을 ret에 더하고 ai를 그만큼 감소시켜 누적합이 -1이 되도록 만듭니다.
- sum을 갱신한 후 s의 부호를 반전시킵니다.
- 시작 부호가 양수인 경우와 음수인 경우 각각 계산한 뒤, 더 작은 값을 반환합니다.
C++ 코드 구현
다음은 위 알고리즘을 구현한 전체 C++ 코드입니다.
#include <bits/stdc++.h>
using namespace std;
int util(vector<int> A, int s){
int n = A.size();
int ret = 0;
int sum = 0;
for (int ai : A){
int nsum = sum + ai;
if (s > 0){
if (nsum <= 0){
ret += abs(nsum) + 1;
ai = ai + abs(nsum) + 1;
}
} else {
if (nsum >= 0){
ret += nsum + 1;
ai = ai - (nsum + 1);
}
}
sum += ai;
s *= -1;
}
return ret;
}
int solve(vector<int> A){
int res = min(util(A, 1), util(A, -1));
return res;
}
int main(){
vector<int> A = { 1, -3, 1, 0 };
cout << solve(A) << endl;
}
입력
{ 1, -3, 1, 0 }
출력
4
복잡도 분석
이 알고리즘은 배열을 상수 시간에 두 번 순회하므로 시간 복잡도는 O(N)입니다. 함수에 벡터가 값으로 전달되므로 추가 공간 복잡도는 O(N)이지만, 매개변수를 참조(&)로 전달하도록 수정하면 O(1)의 추가 공간만으로 최적화할 수 있습니다.