숫자 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억에 가까운 수이기 때문에, 1,023,456,789 부터 이 값까지의 범위를 루프도는 것은 수십억번의 루프를 돌아야 하니 그리 좋은 접근이 아니다. 0-9 팬디지털은 0~9의 숫자들의 순열로 만들어 지는데 이 중에서 10자리가 되지 않는 (첫번째 숫자가 0인) 것을 제외하면 범위를 제법 줄일 수 있다.
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 개나 되기 때문에 위 코드 역시 실행에 상당한 시간이 요구된다. 반복 횟수를 어떻게 더 줄일 수 있을까?
예를 들어 1425…. 로 시작하는 팬디지털들을 생각해보자. 이들은 모두 d4가 짝수가 아니기 때문에 첫번째 조건을 만족하지 않는다. 그렇다면 이렇게 시작하는 모든 순열들은 더 이상 검사할 필요가 없다. 그리고 이렇게 걸러버리면 한 번에 720개 (5 이후의 순열의 가짓수)의 검사를 생략할 수 있다. 즉 앞자리의 보초가 걸리는 경우 뒷자리의 숫자들을 검사하지 않도록 하는 방법이 필요하다.
성능을 위한 다른 접근
아래 코드는 아주 예전에 작성한 것으로, 순열을 만드는 리스트 축약식을 사용하면서 각자리 숫자들의 생성 조건을 일일이 걸어주는 방식을 취했다. 이렇게하면 수행시간은 매우 크게 단축할 수 있는데, 문제는 코드가 너무 지저분하다는 것이다.
from functools import reduce
toInt = lambda xs: reduce(lambda x, y: 10 * x + y, xs)
%%time
check = lambda xs, a: (100*xs[0] + 10*xs[1] + xs[2]) % a == 0
ds = [(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(map(toInt, ds)))제너레이터를 사용한 풀이
위의 코드가 성능 측면에서는 개선이 있지만, 코드가 너무 지저분하기에 다른 방법으로 접근해보기로 한다. 성능 측면에서의 핵심은 앞자리 숫자가 조건을 만족하지 않으면 그 뒤의 숫자들을 검사하지 않고 건너뛰는 것인데, 순열을 생성하는 제너레이터를 약간 변형하여 그 내부에 검사로직을 추가해주면 된다. 누적된 부분 순열의 끝 3개 숫자를 검사하여 조건을 만족하지 않으면 제너레이터가 값을 yield 하지 않고 리턴하면 되는 것이다.
def gen(acc, xs, k):
# acc : 누적된 순열
# xs : 남아있는 숫자
# k : 남은 단계
dividers = [1, 2, 3, 5, 7, 11, 13, 17]
# 맨 앞자리에는 0이 올 수 없음
if len(acc) > 0 and acc[0] == 0:
return
# 3개 이상이 모였을 때 뒤 3개 숫자를 연결하여 검사
if len(acc) > 3:
a, b, c = acc[-3:]
if (100 * a + 10 * b + c) % dividers[len(acc) - 3] > 0:
return
# 10 개 숫자가 모였고, 조건을 만족하면 yield
if k == 0:
yield acc
return
# 남은 숫자를 계속 누적하여 yield
for i, x in enumerate(xs):
yield from gen((*acc, x), (*xs[:i], *xs[i+1:]), k - 1)
def toInt(xs):
res = 0
for x in xs:
res = res * 10 + x
return res
%time print(sum(map(toInt, gen((), tuple(range(10)), 10))))
# 16695334890
# elapsed: 31 ms