배열의 합과 곱을 0이 아니게 만드는 최소 연산 횟수를 구하는 C++ 프로그램

문제 설명

n개의 원소로 이루어진 배열 A가 있다고 가정해 보겠습니다. 한 번의 연산으로 배열에 있는 임의의 원소 하나에 1을 더할 수 있습니다. 만약 배열 전체 원소의 합 또는 곱이 0이라면, 두 값이 모두 0이 아니게 될 때까지 연산을 반복해야 합니다. 이때 필요한 최소 연산 횟수를 구하는 것이 이 문제의 목표입니다.

예시

입력이 A = [-1, 0, 0, 1]일 때 정답은 2입니다. 현재 배열의 곱과 합이 모두 0이기 때문입니다. 값이 0인 두 번째와 세 번째 원소에 각각 1을 더하면 배열은 [-1, 1, 1, 1]이 되며, 이때 합은 2, 곱은 -1로 조건을 만족하게 됩니다.

접근 방법

이 문제는 그리디(greedy) 기법으로 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 곱이 0이 되지 않으려면 값이 0인 원소는 반드시 1씩 증가시켜야 합니다.
• 따라서 기본적으로 필요한 연산 횟수는 배열 안의 0의 개수(cnt)입니다.
• 모든 0을 없앤 후의 합은 (기존 합 + cnt)가 됩니다. 이 값이 0이라면 합 조건을 만족하지 못하므로, 임의의 원소에 1을 한 번 더 더하는 추가 연산이 필요합니다. 이 경우 정답은 cnt + 1입니다.

풀이 단계

위 아이디어를 의사 코드로 표현하면 다음과 같습니다.

sum := 0
cnt := 0
n := size of A
for i := 0 to n-1 do:
    x := A[i]
    sum := sum + x
    cnt := cnt + (x == 0 ? 1 : 0)
return (sum + cnt == 0 ? cnt + 1 : cnt)

C++ 구현 예제

아래는 위 로직을 C++로 구현한 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
    int sum = 0, cnt = 0;
    int n = A.size();
    for (int i = 0; i < n; i++) {
        int x = A[i];
        sum += x;
        cnt += x == 0 ? 1 : 0;
    }
    return sum + cnt == 0 ? cnt + 1 : cnt;
}

int main() {
    vector<int> A = { -1, 0, 0, 1 };
    cout << solve(A) << endl;
}

실행 결과

입력

{ -1, 0, 0, 1 }

출력

2

마무리

이 알고리즘은 배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)입니다. 0의 개수를 먼저 세고, 마지막에 합이 0이 되는 경우에만 추가 연산 여부를 판단하면 되기 때문에 매우 효율적인 풀이입니다.