합과 곱을 0과 다르게 만드는 데 필요한 단계 수를 계산하는 C++ 프로그램

n개의 요소가 있는 배열 A가 있다고 가정합니다. 한 번의 작업으로 A에 미리 설정된 하나의 요소로 1을 더할 수 있습니다. 배열에 있는 모든 요소의 합이나 곱이 0이면 이 작업을 한 번 더 수행할 수 있습니다. 배열에 있는 모든 요소의 합과 곱을 모두 0과 다르게 만드는 데 필요한 최소 단계 수를 계산해야 합니까?

따라서 입력이 A =[-1, 0, 0, 1]과 같으면 곱과 합계가 모두 0이므로 출력은 2가 됩니다. 두 번째와 세 번째 요소에 1을 더하면 배열은 [−1,1,1,1]이면 합은 2와 같을 것이고 곱은 -1과 같을 것입니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

sum := 0
cnt := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
   x := A[i]
   sum := sum + x
   cnt := cnt + (if x is same as 0, then 1, otherwise 0)
return (if sum + cnt is same as 0, then cnt + 1, otherwise cnt)

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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