Project Euler 問題31

pe_31.pl

#!/usr/bin/perl

use strict;
use warnings;

my $target = shift;
my @coins = (200, 100, 50, 20, 10, 5, 2, 1);
my @sets = ();
my $ans = 0;

# 通貨ごとのコインの組み合わせ(0～200枚)を予め作っておく
foreach my $coin (@coins)
{
  my @arr = ();
  for (my $i=0; $i<=($target/$coin); $i++)
  {
    push(@arr, $coin*$i);
  }
  push(@sets, \@arr);
}

# コインのセットで総当り
my $s = $sets[0];
for(my $i=1; $i <= $#sets; $i++)
{
  $s = _add($s, $sets[$i]);
}
print "Ans: $ans\n";
exit;

#
# _add: 合計金額がtargetの範囲内で総当りで加算
#   argv[0]: 合計金額配列
#   argv[1]: 加算値配列
#
sub _add {
  my ($sums, $val) = @_;
  my $tmp = ();
  foreach my $s (@$sums) {
    foreach my $v (@$val) {
      my $sum = $s + $v;
      if($sum >= $target)
      {
        #加算した結果が目標金額ピッタリの場合のみ答えとしてカウント
        if($sum == $target)
        {
          $ans++;
        }
        last;
      }
      else
      {
        #目標金額未満なので次のコインに残す
        push(@$tmp, $sum);
      }
    }
  }
  return $tmp;
}

# Ans: 73682

再帰でやったらえらいこっちゃ時間がかかったので苦肉の策。

確率統計生理的にダメなので自分にとっては難しかったです。