오각수는 Pn = n (3n − 1)/2 라는 공식으로 구할 수 있고, 처음 10개의 오각수는 다음과 같습니다.
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …
위에서 P4 + P7 = 22 + 70 = 92 = P8이 됨을 볼 수 있습니다. 하지만 두 값의 차인 70 − 22 = 48 은 오각수가 아닙니다.
합과 차도 모두 오각수인 두 오각수 Pj, Pk 에 대해서, 그 차이 D = | Pk − Pj | 는 가장 작을 때 얼마입니까?
오각수 생성과 판별만 할줄 알면 풀수는 있지만…
정공법으로 가면 너무 오래걸린다.
가장 처음 나오는 $d값이 정답인걸 안다면 약 4초만에 문제가 해결되겠지만, 그렇지 않으면 족히 30분은 기다려야 답이 나올 것이다.
아래의 코드는 처음 나오는 값이 답이라는 것을 상정한 채 문제를 해결한 것이다.
만약 그렇지 않다면, getp 함수와 isp 함수를 캐싱하여 문제를 해결하고,
12열의 for문을 reverse하여 $p-$tp > $d 이면 last하여 쓸데없는 반복을 줄임으로서 시간을 좀 더 단축시킬 수 있겠다.
|
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; use Scalar::Util::Numeric qw(:all); my $c = 0; my $d = 9**9**9; while(3*$c-2 <= $d) { my $p = getp(++$c); for (1..$c) { my $tp = getp($_); if (isp($p-$tp) and isp($p+$tp) and $p-$tp < $d) { $d = $p-$tp; say $p-$tp; exit; # 첫번째가 답인걸 안다고 하면, 끝낸다. } } } sub getp { my $n = shift; return $n*(3*$n-1)/2; } sub isp { my $p = shift; return isint((1+sqrt(1+24*$p))/6); } |