Project Euler - Problem 31

問題

• 原文

  How many different ways can £2 be made using any number of coins?

• 日本語訳

  いくらかの硬貨を使って2ポンドを作る方法はいくつあるでしょうか?

解答

ポンドとペンスを別々に扱うのは面倒と無駄以外の何者でもないので、単位をペンスに統一します。よって問題は合計が200ペンスとなるコインの組み合わせは何通りあるかです。

コインを昇順にC_i(i = 0, 1, 2, ..., 7)と番号づけることにします。 合計nペンスとなるC_k以下のコインを使った組み合わせをcc(n, k)と表すと、次のようになります：

1. cc(0, k) = 1
2. cc(n, 1) = 1
3. cc(n, k) = Σ(cc(n - iC_k, k - 1))、ただしi ∈ { 0 , 1, 2, ..., floor(n / C_k) }

副問題は同じものが何度も出てくるのでメモ化しています。

#!/usr/bin/env perl

use strict;
use warnings;
use feature qw/say state/;
use List::Util qw/sum/;

sub coin_comb($;$);
{
  my @coins = (1, 2, 5, 10, 20, 50, 100, 200);
  sub coin_comb($;$) {
    state %memos;
    my ($currency, $coin_idx) = @_;
    $coin_idx //= $#coins;

    return $memos{$currency, $coin_idx} if exists $memos{$currency, $coin_idx};
    return 1 if $currency == 0;
    return 1 if $coin_idx == 0;

    use integer;
    $memos{$currency, $coin_idx} = sum map {
      coin_comb($currency - $coins[$coin_idx] * $_, $coin_idx - 1);
    } 0 .. $currency / $coins[$coin_idx];
  }
}
say coin_comb 200;