C++で削除が必要な箱の数を求めるアルゴリズム

問題概要

この問題では、各要素が箱の山（それぞれの高さは1単位）を表す配列 arr[] が与えられます。私たちの課題は、削除する必要がある箱の数を求めることです。

人は配列のインデックス0の位置に、その山の高さの地点に立っており、配列の末尾まで移動する必要があります。ある山から隣の山へ移動するには、ジャンプを行います。

ジャンプが許されるのは、次の山の高さが現在と同じか、それより低い場合のみです。もし次の山の方が高ければ、高さが揃うまでその山から箱を取り除かなければなりません。つまり、先頭の山から最後の山まで移動する過程で取り除く箱の総数を求めるのが目的です。

例を使って問題を理解しましょう。

入力 : arr[] = {5, 7, 3, 1, 2}
出力 : 3

解説

初期状態では、人のいる高さは5です。

ステップ1 − 高さ7の2番目の位置へ移動するには、2個の箱を取り除く必要があります。

ステップ2 − 高さ3の3番目の位置へは、箱を取り除く必要はありません。

ステップ3 − 高さ1の次の位置へも、箱を取り除く必要はありません。

ステップ4 − 高さ2の次の位置へ移動するには、1個の箱を取り除きます。これにより、削除した箱の合計は3個になります。

解法アプローチ

この問題に対するシンプルな解法は、配列を先頭から末尾まで走査し、次の要素が現在の要素より大きいかどうかを確認することです。大きい場合は、その差を削除する箱の総数を保持する変数 boxesRemoved に加算していきます。最後に boxesRemoved を返せば答えが得られます。

この方法の計算量は O(n)、空間計算量は O(1) であり、非常に効率的です。

実装例

ソリューションの動作を示すプログラム：

#include <iostream>
using namespace std;
int findBoxesRemoved(int arr[], int n){
    int boxesRemoved = 0;
    for (int i = 0; i < n-1; i++) {
        if (arr[i] < arr[i+1])
            boxesRemoved += (arr[i+1] - arr[i]);
    }
    return boxesRemoved;
}
int main(){
    int arr[] = { 5, 7, 3 , 1, 2, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"ゴールまで到達するために削除する必要のある箱の総数は "<<findBoxesRemoved(arr, n);
    return 0;
}

出力

ゴールまで到達するために削除する必要のある箱の総数は 7