C++で配列の数字から作る2つの数値の合計を最小化する方法

問題の概要

0から9までの値を含む数字の配列が与えられます。この問題では、配列内のすべての数字を使って2つの数値を作り、その合計が最小になるようにすることが求められます。重要な制約として、与えられた配列のすべての数字を必ず使用しなければなりません。

例

入力配列が {7, 5, 1, 3, 2, 4} の場合、最小合計は 382 となります。これは、135 と 247 という2つの数値を作成できるためです（135 + 247 = 382）。

アルゴリズムの考え方

この問題は貪欲法（グリーディ法）で解くことができます。合計を最小にするには、小さい桁の数字ほど大きな位（上位の桁）に配置するのが最適だからです。手順は以下の通りです。

• 配列を昇順にソートします。
• ソート済みの配列から、偶数インデックスと奇数インデックスの数字を交互に取り出し、それぞれ別の数値を構成します。これにより、小さい数字が2つの数値の上位の桁に均等に分散されます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int getMinSum(int *arr, int n) {
    sort(arr, arr + n);
    int a = 0;
    int b = 0;
    for (int i = 0; i < n; ++i) {
        if (i % 2 == 0) {
            a = a * 10 + arr[i];
        } else {
            b = b * 10 + arr[i];
        }
    }
    return a + b;
}
int main() {
    int arr[] = {7, 5, 1, 3, 2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum sum = " << getMinSum(arr, n) << endl;
    return 0;
}

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

実行結果

Minimum sum = 382

計算量について

このアルゴリズムの時間計算量は、ソート処理が支配的となるため O(n log n) です。空間計算量は追加の配列を使用しないため O(1) となります。数字を交互に振り分けることで、両方の数値の桁数の差が最大1桁に抑えられ、結果として合計が最小になります。