C++で指定金額ちょうどで商品を購入できるか判定する方法

ある数値 N が与えられたとします。ケーキ売り場では、ケーキが1つ40ルピー、ドーナツが1つ70ルピーで販売されています。このとき、所持金 N ルピーを使って、これらの商品をちょうど N ルピ―ぴったりで購入できるかどうかを判定します。

例えば、N = 110 の場合、40 + 70 = 110 となるため、出力は True（購入可能）になります。

解決のアプローチ

この問題は、深さ優先探索（DFS）を用いて解くことができます。基本的な考え方は以下の通りです。

• 現在の合計金額 i を引数として DFS を実行します。
• i が n より大きければ、その経路は失敗なので false を返します。
• i が n と等しければ、ちょうどの金額に到達できたので true を返します。
• そうでなければ、「i + 40（ケーキを買う）」と「i + 70（ドーナツを買う）」の2つの分岐を再帰的に試します。

アルゴリズムの手順

o := false
関数 dfs(i) を定義する
もし i > n ならば:
    return false
もし i == n ならば:
    return true
もし dfs(i + 40) が真ならば:
    return true
return dfs(i + 70)
main メソッドから以下を実行する
n := N
o := dfs(0)
return o

C++による実装例

それでは、実際の実装を見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
int n;
bool o = false;

bool dfs(int i) {
   if (i > n)
      return false;
   if (i == n)
      return true;
   if (dfs(i + 40))
      return true;
   return dfs(i + 70);
}
bool solve(int N) {
   n = N;
   o = dfs(0);
   return o;
}
int main(){
   int N = 110;
   cout << solve(N) << endl;
}

入力

110

出力

1

出力が 1（true）となっており、110ルピーちょうどでケーキ1つとドーナツ1つを購入できることが確認できます。

補足：計算量について

この DFS アプローチはシンプルですが、N が大きい場合は指数的な探索になる可能性があります。実際には「40a + 70b = N を満たす非負整数 a, b が存在するか」という問題に帰着できるため、N を10の倍数で割った余りや、線形方程式の整数解の存在チェックによって、O(1) 〜 O(N) 程度で効率的に判定することも可能です。