C++를 사용하여 이진 문자열 S로 합계하는 데 필요한 최소 연산 수입니다.

문제 설명

주어진 이진 문자열 str. str이 나타내는 수를 생성하기 위해 수행해야 하는 최소 연산 수를 찾으십시오. 다음 작업만 수행할 수 있습니다. -

• 2 ^x 추가
• 2 ^x 빼기

바이너리 문자열이 "1000"이면 1번의 작업만 수행하면 됩니다. 즉, 2 ³ 추가

이진 문자열이 "101"이면 2개의 작업(예:2 ² 추가)을 수행해야 합니다. + 2 ⁰

예

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int getMinOperations(string s){
   reverse(s.begin(), s.end());
   int n = s.length();
   int result[n + 1][2];
   if (s[0] == '0') {
      result[0][0] = 0;
   } else {
      result[0][0] = 1;
   }
   result[0][1] = 1;
   for (int i = 1; i < n; ++i) {
      if (s[i] == '0') {
         result[i][0] = result[i - 1][0];
         result[i][1] = 1 + min(result[i - 1][1],
         result[i - 1][0]);
      } else {
         result[i][1] = result[i - 1][1];
         result[i][0] = 1 + min(result[i - 1][0],
         result[i - 1][1]);
      }
   }
   return result[n - 1][0];
}
int main(){
   string str = "101";
   cout << "Minimum required operations = " << getMinOperations(str) << endl;
   return 0;
}

출력

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

Minimum required operations = 2