영국의 화폐 단위는 파운드(£)와 펜스(p)이고, 동전의 종류는 아래와 같습니다.
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p)
이 동전들을 가지고 2파운드를 만드는 방법은 다양할 것입니다. 예를 하나 들면 이렇습니다.1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
2파운드를 만드는 서로 다른 방법은 모두 몇가지나 있습니까?
사실 슬슬 귀찮았다.
동적계획법을 쓰면 좋았겠지만, 귀찮으니까 그냥 바보같이 짰다.
실행시간은 약 2초
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#!/usr/bin/env perl use 5.010; use strict; use warnings; my $r = 0; for my $h (-1..200) { next if ($h == -1); for my $g (-1..max(0, 200 - (200*$h))) { next if ($g == -1); for my $f (-1..max(0, 200 - (100*$g + 200*$h))) { next if ($f == -1); for my $e (-1..max(0, 200 - (40*$f + 100*$g + 200*$h))) { next if ($e == -1); for my $d (-1..max(0, 200 - (20*$e + 40*$f + 100*$g + 200*$h))) { next if ($d == -1); for my $c (-1..max(0, 200 - (10*$d + 20*$e + 40*$f + 100*$g + 200*$h))) { next if ($c == -1); for my $b (-1..max(0, 200 - (4*$c + 10*$d + 20*$e + 40*$f + 100*$g + 200*$h))) { next if ($b == -1); for my $a (-1..max(0, 200 - (2*$b + 4*$c + 10*$d + 20*$e + 40*$f + 100*$g + 200*$h))) { next if ($a == -1); $r++ if (200 == 1*$a + 2*$b + 5*$c + 10*$d + 20*$e + 50*$f + 100*$g + 200*$h); }}}}}}}} # sorry...! say $r; sub max { return $_[0] > $_[1] ? $_[0] : $_[1]; } |