【C++】数値nを表すときに使う「異なる桁」の種類を最小にする方法

ある整数 n が与えられたとします。この n を、0 以外の桁（1〜9）の和として分解することを考えます。その際、「使用する異なる数字の種類数」が最小になるような解を見つけるのが本記事のテーマです。

例えば入力が n = 13 の場合、出力は次のようになります。

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

これは「1」を 13 個並べたものです。合計は 13 となり、使用している数字は「1」の 1 種類だけなので、種類数の観点で最適な解となります。

解法のアプローチ

この問題は非常にシンプルです。少なくとも 1 種類の数字は必ず必要となるため、1 種類だけで n を表せればそれが最適解です。そこで、すべてを「1」で構成すればよいことになります。手順は以下の通りです。

• 変数 i を 0 から n 未満まで 1 ずつ増やしながらループする
• 各ループ内で「1」を出力する

C++での実装例

理解を深めるために、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void solve(int n){
    for (int i = 0; i < n; i++)
        printf("1, ");
}
int main(){
    int n = 13;
    solve(n);
}

入力

13

出力

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

補足：計算量と応用

この解法の時間計算量は O(n) です。なお、もし「出力する要素の個数」を減らしたい場合は、9 をできるだけ多く使い残りを他の数字で埋める方法も考えられます。しかし本問題の目的はあくまで「異なる数字の種類数の最小化」であるため、1 のみを使用するこの方法が最もシンプルかつ確実な解となります。