3040

すべての硬貨の価値は任意の自分より小さい額の硬貨の価値で割り切れるとする。このとき、硬貨の価値と枚数が与えられるので、お釣りはないものとして、指定された額を何回まで支払えるか答えよ、という問題。

大きい額の硬貨から使うことを考える。お釣りがもらえないので、指定された額以上の価値がある硬貨については、他に何かを追加する必要はない。それ以外の硬貨を使う場合、自分より価値の小さい硬貨については、自分の額を割り切るように設定されているので、ぴったり払えるならば払ってしまって良い。これは自分を他の通過でぴったり置き換えることができるためである。

同様の理屈で、ある払い方で不足がある場合、自分を使わずに別の払い方をしても、同じ不足が出るので、不足分を支払うことを考えるときに他の払い方に配慮する必要はない。(貪欲に決めていい。)なので、ぴったり払えるように不足分を捻出する。もし自分より価値の小さい硬貨を使ってもぴったり払えない場合は、支払えるようになるのに必要な一番小さい額の硬貨を追加する。(このとき、追加した硬貨によって、より小さい硬貨を一部使わないで済むようにできるが、結局それを再利用したところでまた同じ額の不足が発生するので、ここで切り捨ててしまって問題ない。)

以上を整理すると、大きい方の硬貨から、自分を1枚以上使い、できるだけ超過しないように支払う。このとき不足していても構わない。不足分がある場合は、できるだけ超過しないように、自分よりも小さい額の硬貨を選択していく。どうしてもぴったりにならない場合には、超過する最少額の硬貨を追加する。(高速化のために、同様の支払いをできる限り繰り返す。)このプロセスを硬貨がなくなるか、支払い方がなくなるまで繰り返せば良い。