C++で指定された桁数と桁の合計から最小の数値を求める方法

問題概要

この問題では、「sum（各桁の合計）」と「digit（桁数）」という2つの値が与えられます。求めるのは、指定された桁数を持ち、かつ各桁の合計がsumと一致するような最小の数値です。

具体例で問題を確認しましょう。

入力

sum = 15, digit = 2

出力

69

説明

桁の合計が15となる2桁の数は、69、78、87、96の4つです。この中で最も小さい数は69であるため、答えは69となります。

解法アプローチ

最も単純な解法は、指定された桁数を持つすべての数を順に調べ、桁の合計がsumと一致する最小の数を見つける方法です。しかし、この方法は探索範囲が膨大になるため非効率です。

そこで有効なのが貪欲法（グリーディー法）を用いたアプローチです。数値を下位の桁（LSB）から順に構築していきます。まず最下位の桁に可能な限り大きい数字を割り当て、その後、次の桁へと進んでいきます。

ポイントは、下位の桁をできるだけ大きく、上位の桁（MSB）をできるだけ小さく保つことです。これにより、全体として最小の数値を作り出すことができます。

コードの解説

まず、sumが0の場合や、sumが9×digitを超える場合（その桁数では表現不可能）は解が存在しないため、その旨を出力して終了します。解が存在する場合は、先頭の桁用に1を確保し（sumから1を減算）、残りの桁を末尾から順にできるだけ大きな数字（最大9）で埋めていきます。最後に、先頭の桁に残りの値+1を代入します。

解法の動作を示すプログラム：

例

#include <iostream>
using namespace std;
void findSmallestNumWithSum(int digit, int sum) {
   if (sum == 0) {
      if(digit == 1)
         cout<<"Smallest number is 0";
      else
         cout<<"Smallest number with sum cannot be found";
      return ;
   }
   if (sum > 9*digit) {
      cout<<"Smallest number with sum cannot be found";
      return ;
   }
   int number[digit];
   sum -= 1;
   for (int i = digit-1; i>0; i--) {
      if (sum > 9) {
         number[i] = 9;
         sum -= 9;
      } else {
         number[i] = sum;
         sum = 0;
      }
   }
   number[0] = sum + 1;
   cout<<"Smallest number is ";
   for (int i=0; i<digit; i++)
      cout<<number[i];
}
int main() {
   int sum = 15, digit = 3;
   findSmallestNumWithSum(digit, sum);
   return 0;
}

出力

Smallest number is 159

実行結果の流れ

sum=15、digit=3の場合、まず先頭の桁用に1を確保して残りは14になります。末尾の桁から順に処理すると、3桁目に9を割り当てて残りは5、2桁目に5を割り当てて残りは0となり、最終的に先頭の桁は0+1=1となります。よって、答えは「159」が出力されます。