숫자 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 팬디지털을 모두 찾아서 그 합을 구하면 얼마입니까?
http://euler.synap.co.kr/prob_detail.php?id=43
접근
문제 그대로를 코딩하면 간단하게 답을 낼 수 있을 것 같다.
가장 큰 0-9 팬디지털 수는 9,876,543,210 으로 100억에 가까운 수이기 때문에, 이 범위를 루프도는 것은 그리 좋은 생각이 아니다. 그래서 나름 머리를 쓴다고 써서, (0~9)의 숫자들로 만들 수 있는 순열을 사용해서 루프를 돌면서, 만들어진 순열로 N을 생성하고, 앞에서부터 3자리씩 끊은 수를 만들어내어 소수들로 나눠지는지를 검사했다. 물론 검사 횟수를 줄이기 위해서 10자리가 되지 않은 N은 건너뛴다.
from itertools import permuations
from functools import reduce
qs = (2, 3, 5, 7, 11, 13, 17)
res = []
for ds in permuations(range(10)):
if ds[0] == 0: # 0-9 팬디지털수가 아님
break
n = reduce(lambda x, y: x * 10 + y, ds)
ws = [((n // 10**i) % 1000) for i in range(7, -1, -1)]
if all(filter(lambda x: x[0] % x[1] == 0, zip(ws, qs))):
res.append(n)
print(sum(res))문제는 이렇게 해도 이미 0-9 팬디지털 수의 개수가 3,265,920 개나 되기 때문에 위 코드는 실행에 상당한 시간이 걸린다. 결과는 올바르게 계산하지만, 시간을 더 단축하려면 어떻게 해야할까? 보초를 몇 가지 더 세워서 계산할 필요가 없는 경우를 건너 뛰도록 하자. 2, 3, 5의 배수는 간단한 체크로 배수 여부를 판별할 수 있다. 이러한 보초를 앞에 배치해서 건너뛰도록하면 성능을 대폭 개선할 수 있다.
from itertools import permuations
from functools import reduce
qs = (2, 3, 5, 7, 11, 13, 17)
res = []
for ds in permuations(range(10)):
if ds[0] == 0: # 0-9 팬디지털수가 아님
continue
if ds[3] % 2 == 1: # d2 d3 d4 가 짝수가 아님
continue
if sum(ds[2:5]) % 3 != 0: # d3 d4 d5가 3의 배수가 아님
continue
if ds[5] % 5 != 0: # d4 d5 d6가 5의 배수가 아님
continue
n = reduce(lambda x, y: x * 10 + y, ds)
ws = [((n // 10**i) % 1000) for i in range(7, -1, -1)]
if all(filter(lambda x: x[0] % x[1] == 0, zip(ws, qs))):
res.append(n)
print(sum(res))성능을 위한 다른 접근
최근의 PC 성능에서는 사실 이정도로 보초를 이용하는 것으로도 1초 이내에 답을 낼 수 있다. 그러나 10년 전쯤의 PC 성능으로는 이 로직 역시 한참 부족한 성능이었다. 위 로직의 가장 큰 맹점은 10! 개나 되는 루프를 일단 돈다는 것이다. 앞에서 보초를 세워서 복잡한 연산을 조금 줄이기는 하지만 루프의 횟수 자체가 많다는 사실은 변하지 않는다. 따라서 복합 루프를 통해서 특정한 자리에 필요한 숫자만 사용하도록 하면 더 시간을 줄일 수 있다. (대신 코드는 좀 더 지저분해진다.)
리스트 축약 문법 내에서는 2개 이상의 루프를 한 번에 지정할 수 있는데, 이 방법을 사용해서 각 자리 숫자로 올 수 있는 것만 제한하거나, 제외할 수 있는 것들은 미리 제외한다. 앞 부분에서 제외된 숫자 이후에 딸리는 순열들은 이 방법에서는 아예 루프 대상에서 제외되기 때문에 전체 루프 횟수는 크게 감소한다.
%%time
compose = lambda xs: reduce(lambda x, y: x * 10 + y, xs)
ds = [compose((d1, d2, d3, d4, d5, d6, d7, d8, d9, d10))
for d1 in range(1, 10)\
for d2 in range(10) if d1 != d2\
for d3 in range(10) if d3 not in (d1, d2)\
for d4 in range(0, 10, 2) if d4 not in (d1, d2, d3)\
for d5 in range(10) if d5 not in (d1, d2, d3, d4) and check((d3, d4, d5), 3)\
for d6 in (0, 5) if d6 not in (d1, d2, d3, d4, d5)\
for d7 in range(10) if d7 not in (d1, d2, d3, d4, d5, d6) and check((d5, d6, d7), 7)\
for d8 in range(10) if d8 not in (d1, d2, d3, d4, d5, d6, d7)\
and check((d6, d7, d8), 11)\
for d9 in range(10) if d9 not in (d1, d2, d3, d4, d5, d6, d7, d8)\
and check((d7, d8, d9), 13)\
for d10 in range(10) if d10 not in (d1, d2, d3, d4, d5, d6, d7, d8, d9)\
and check((d8, d9, d10), 17)
]
print(sum(ds))