C++でのY未満の数のセットの最小数

問題の説明

連続する数字の文字列と数字のYが与えられた場合、タスクは、すべてのセットが以下のルールに従うように最小セットの数を見つけることです-

• セットには連続した数字が含まれている必要があります
• 数字を複数回使用することはできません。
• セット内の数はYを超えてはなりません。

例

str =“ 1234”およびY =20の場合、以下のセットが作成されるため、答えは3です-

{12}{3}および{4}

アルゴリズム

• 文字列を数値に変換
• 数値がY以下の場合は、f=1とマークします
• 数値がYを超える場合は、f =1の場合はカウントを増やし、fを0として再初期化し、numをs [i]-‘0’またはnumを0として初期化します
• 文字列を完全に反復した後、fが1の場合はカウントを増やします

例

#include <iostream>
#include <string>
using namespace std;
int getMinSets(string str, int y) {
   int cnt = 0;
   int num = 0;
   int l = str.length();
   int f = 0;
   for (int i = 0; i < l; ++i) {
      num = num * 10 + str[i] - 48;
      if (num <= y) {
         f = 1;
         continue;
      }
      if (f) {
         ++cnt;
      }
      num = str[i] - '0';
      f = 0;
      if (num <= y) {
         f = 1;
      } else {
         num = 0;
      }
   }
   if (f) {
      ++cnt;
   }
   return cnt;
}
int main() {
   string str = "1234";
   int y = 20;
   cout << "Minimum sets = " << getMinSets(str, y) << endl;
   return 0;
}

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Minimum sets = 3