숫자 0을 만드는 데 필요한 최소 작업 수를 찾는 C++ 프로그램

<시간/>

n자리의 숫자 문자열 S가 있다고 가정합니다. S가 디지털 시계를 나타내고 전체 문자열이 0에서 10^n - 1 사이의 정수를 표시한다고 가정합니다. 자릿수가 적을 경우 선행 0이 표시됩니다. 작업을 따르십시오 -

시계의 숫자를 1로 줄이십시오. 또는
두 자리 숫자 바꾸기

필요한 최소한의 작업으로 시계가 0으로 표시되기를 원합니다. 이를 수행하는 데 필요한 작업 수를 계산해야 합니다.

따라서 입력이 S ="1000"과 같으면 출력은 2가 됩니다. 처음 1을 마지막 0으로 바꿀 수 있으므로 문자열은 "0001"이 됩니다. 이제 문자열을 1 줄여 "0000"을 얻습니다.

단계

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

n := size of S
x := digit at place S[n - 1]
for initialize i := 0, when i <= n - 2, update (increase i by 1), do:
   if S[i] is not equal to '0', then:
      x := x + (digit at place S[i]) + 1
return x

예

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

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

int solve(string S) {
   int n = S.size();
   int x = S[n - 1] - '0';
   for (int i = 0; i <= n - 2; i++)
      if (S[i] != '0')
         x = x + S[i] + 1 - '0';
   return x;
}
int main() {
   string S = "1000";
   cout << solve(S) << endl;
}

입력

"1000"