Created
August 22, 2012 07:14
-
-
Save kiyotune/3423293 to your computer and use it in GitHub Desktop.
Project Euler 問題31
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
確率統計生理的にダメなので自分にとっては難しかったです。