Problem 18
何番やっているのかわからなくなってきたけど、18番。
時間がかかるであろうっていうのとそうでないを書いてみた。
時間がかかるってやつは 67番だと再帰使い過ぎでエラーになりますね。
#!/usr/bin/perl use strict; use warnings; my $depth = 15; my $max = 0; my @input = ( [75], [95, 64], [17, 47, 82], [18,35,87,10], [20,4,82,47,65], [19,1,23,75,3,34], [88,2,77,73,7,63,67], [99,65,4,28,6,16,70,92], [41,41,26,56,83,40,80,70,33], [41,48,72,33,47,32,37,16,94,29], [53,71,44,65,25,43,91,52,97,51,14], [70,11,33,28,77,73,17,78,39,68,17,57], [91,71,52,38,17,14,91,43,58,50,27,29,48], [63,66,4,68,89,53,67,30,73,16,69,87,40,31], [4,62,98,27,23,9,70,98,73,93,38,53,60,4,23] ); print "Answer is ", max_sum2(15) , "\n"; # Answer is 1074 sub max_sum2 { my ($limit) = @_; my @array; $limit--; for my $i (0..$limit) { for my $j (0..$i) { my $sum; if ($i == 0){ $sum = $input[0][0]; } elsif ($j == 0) { $sum = $array[$i-1][0] + $input[$i][0]; } elsif ($j == $i) { $sum = $array[$i-1][$j-1] + $input[$i][$j]; } else { my $bigger = ($array[$i-1][$j-1] > $array[$i-1][$j]) ? $array[$i-1][$j-1] : $array[$i-1][$j]; $sum = $bigger + $input[$i][$j]; } push @{$array[$i]}, $sum; } } my ($answer) = (sort {$b <=> $a}@{$array[$limit]})[0]; return $answer; } sub max_sum { my ($depth, $n, $sum) = @_; if ($depth == 15) { $max = $sum if $sum > $max; return $max; } else { max_sum(($depth + 1), $n, $sum + $input[$depth][$n]); max_sum(($depth + 1), ($n + 1), $sum + $input[$depth][$n + 1]) if $depth != 0; } }