この問題は支払い方の最小枚数を求める問題でした。どのような方法で払うのが最適か迷ってしまった方も多いかもしれません。

この問題は動的計画法などの高度なアルゴリズムを用いて解くこともできますが、適切な考察を行うことでこの問題を高速に解くことが出来ます。

解法1. 価値の低い貨幣から決める

実はこの問題は価値の低い硬貨から枚数を決めることが出来ます。

初めに \(1!\) 円硬貨を何枚払うか考えます。 \(2!,3!,\dots,10!\) が全て \(2! = 2\) で割り切れることに注目すると、 \(1!\) 円硬貨を使う枚数は \(P\) を \(2!\) で割った余りを \(r\) として \(2 n + r\) 枚になる必要があるとわかります。(もしそうでない場合、 \(P\) と支払った金額の合計の \(2\) で割った余りが一致しません。)

さらに、もし \(1!\) 円硬貨を \(2\) 枚以上支払った場合、 \(1!\) 円硬貨 \(2\) 枚の代わりに \(2!\) 円硬貨を使った方がより少ない枚数での支払いが可能になるので、最小枚数の支払い方になりません。よって、 \(1!\) 円硬貨は \(r\) 枚使用するとわかります。

同様の議論が \(2!\) 円硬貨から \(10!\) 円硬貨に対しても成り立つので、価値の低い硬貨から枚数を決めて行ってよいことが示されました。よって、上に説明したアルゴリズムを実装すればこの問題を解くことが出来ます。実装は以下の通りです。

• C++

#include <iostream>
using namespace std;

int factorial(int i) { return i ? factorial(i - 1) * i : 1; }

int main() {
  int P;
  cin >> P;

  int answer = 0;
  for (int i = 1; i <= 10; i++) {
    int divisor = factorial(i + 1);
    int residue = P % divisor;
    answer += residue / factorial(i);
    P -= residue;
  }

  cout << answer << "\n";
}

• Python

from math import factorial

P = int(input())
answer = 0

for i in range(1, 11):
  divisor = factorial(i + 1)
  residue = P % divisor
  answer += residue // factorial(i)
  P -= residue

print(answer)

解法2. 価値の高い貨幣から決める

別解として、貪欲法を用いて価値の高い貨幣を優先して使用していけば最小枚数を達成できます。

理由としてまず先に直感的な説明を行います。日常生活で 50 円玉、 100 円玉と 500 円玉をたくさん持っている状況を考えてみましょう。もしも 850 円のものをちょうどを払って買う場合、自分はまずは 500 円玉を出して、次に 100 円玉を 3 枚出して、最後に 50 円玉を出します。これは、「出来るだけ大きい貨幣を使った方が良さそう」という直感に基づくアルゴリズムに従った結果です。

この上から貪欲に決めるアルゴリズムは実はこの問題でも成り立ちます。正当性を示すために厳密な証明を行います。次の条件を満たす支払い方を「適切な支払い方」として定義します。

• \(1 \leq n \leq 10\) に対して、 \(n!\) 円硬貨は最大でも \(n\) 枚しか使用しない。

  • (証明) 背理法で示します。もしも条件を満たさない場合、ある \(m\) が存在して \(m!\) 円硬貨を \(m+1\) 枚以上支払うことになります。しかし、 \(m!\) 円硬貨を \(m+1\) 枚支払う代わりに \((m+1)!\) 円硬貨を支払う方がより少ない枚数で条件を満たすことになり、矛盾します。

この時、次の事実が導かれます。

• 支払う金額が \(n!\) 円以上であり、最適な支払い方をしているならば、 \(n!\) 円硬貨以上の価値の硬貨を使用している。

  • (証明) 対偶を背理法で示します。 \((n-1)!\) 円硬貨のみを使用している場合、支払える金額の最大は \(1! \times 1 + 2! \times 2 + \dots + (n-1)! \times (n-1) = n! - 1\) 円になり、矛盾します。

この事実から、 \(n=10\) から \(n=1\) の順番で「 \(n!\) が支払う必要のある金額以上であるときは \(n!\) 円硬貨を使用する」とするアルゴリズムの正当性が示されます。

実装は for 文を利用して \(10!\) 円硬貨から \(1!\) 円硬貨の順に降順に調べて行けばよいです。 C++ と Python による実装例は以下の通りです。

• C++

#include <iostream>
using namespace std;

int fac[20];

int main() {
  fac[0] = 1;
  for (int i = 1; i <= 10; i++) {
    fac[i] = fac[i - 1] * i;
  }

  int P, answer = 0;
  cin >> P;

  for (int i = 10; i >= 1; i--) {
    while (P >= fac[i]) {
      answer++;
      P -= fac[i];
    }
  }

  cout << answer << endl;
}

• Python

from math import factorial

P = int(input())
answer = 0
for i in range(10, 0, -1):
  while factorial(i) <= P:
    answer += 1
    P -= factorial(i)
print(answer)