숫자 1406357289은 0 ~ 9 팬디지털인데, 부분열에 관련된 재미있는 성질을 가지고 있습니다.
d1을 첫째 자리수, d2를 둘째 자리수…라고 했을 때, 다음과 같은 사실을 발견할 수 있습니다.
- d2 d3 d4 = 406 → 2로 나누어 떨어짐
- d3 d4 d5 = 063 → 3으로 나누어 떨어짐
- d4 d5 d6 = 635 → 5로 나누어 떨어짐
- d5 d6 d7 = 357 → 7로 나누어 떨어짐
- d6 d7 d8 = 572 → 11로 나누어 떨어짐
- d7 d8 d9 = 728 → 13으로 나누어 떨어짐
- d8 d9 d10 = 289 → 17로 나누어 떨어짐
위와 같은 성질을 갖는 0 ~ 9 팬디지털을 모두 찾아서 그 합을 구하면 얼마입니까?
그냥 문제에서 준 그대로 짜봤다.
마음속으로 둔 제한시간이 1분인데, 약 30초만에 끝났기 때문에 최적화는 하지 않았다.
만약 최적화를 한다면, 직접 나누지 않고 규칙(2의 배수는 끝자리만 확인하면 된다던가)을 이용해서 풀거나, 미리 세자리 수까지 나눗셈 사전을 만들어 놓는다거나 할 수 있겠다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#!/usr/bin/env perl use 5.010; use strict; use warnings; use Math::Permute::Array; my $r = 0; my @a = (0..9); my @p = (2, 3, 5, 7, 11, 13, 17); my $p = new Math::Permute::Array(@a); for my $i (0..$p->cardinal()-1) { my @t = @{$p->permutation($i)}; next if ($t[0] == 0 or $t[3] % 2 == 1 or ($t[5] != 0 and $t[5] != 5)); my $b = 1; for my $j (0..6) { my $k = $t[$j+1]*100+$t[$j+2]*10+$t[$j+3]; $b = 0 if ($k % $p[$j] != 0); } $r += join("", @t) if ($b); } say $r; |