Project Euler #43: Sub-string divisibility

문제를 살펴봅시다.

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d₁ be the 1^st digit, d₂ be the 2^nd digit, and so on. In this way, we note the following:

• d₂d₃d₄=406 is divisible by 2
• d₃d₄d₅=063 is divisible by 3
• d₄d₅d₆=635 is divisible by 5
• d₅d₆d₇=357 is divisible by 7
• d₆d₇d₈=572 is divisible by 11
• d₇d₈d₉=728 is divisible by 13
• d₈d₉d₁₀=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

0부터 9까지 모든 숫자가 한번씩 쓰이는 열자리 수가 있습니다. 첫째자리 숫자를 d_1이라 하고 그다음부터 d_2, d_3..... d_10이라 명합니다. 그리고 위에서 보시다시피 연속된 7개의 소수에 의해 차례대로 나눠진답니다. 이런 조건을 만족하는 Pandigital numbers의 sum을 구하는게 문제의 목표가 되겠습니다.

처음엔 노가다, 즉 brutal force로 풀려고 했습니다. 무식하게 팬디지털수를 다 구해서 (아마 9*9!개를 다 구하겠다는 의지!) 조건에 만족하는 수를 뽑아내서 더하는게 첫번째 생각이었는데, 코드로 구현해내기 귀찮아서 기각.

그 다음에 든 생각은-이 문제를 푼 아이디어인데- 일단 맨 뒤에 올, 조건에 만족하는 세 자리를 구합니다. 즉 1)서로 숫자가 안겹치고, 2)1000이하의 17의 배수를 구했습니다. 그 세자리 수들을 대상으로 리스트를 만들었습니다.

그렇게 만든 세자리수들 앞에 조건에 알맞는 숫자 d_7를 추가했습니다: 만들어진 세자리 중에 안겹치면서, 추가를 해주면 13의 배수를 만들어 줄 수 있는 숫자를 말이죠. 그렇게 네자리 수가 만들어집니다. 그리고 향후 d_6, d_5...들을 결정할 때도1)아직 안쓰인 숫자 중에서 2)차례에 맞는 소수에 의해 나눠지게 해주는지를 고려했습니다. 가장 앞자리, 즉 d_1은 아직 안 쓰인 숫자로 결정이 되고, 마지막 앞자리가 0인 경우는 배제했습니다.

여기 파이썬으로 구현한 코드입니다.

import time

st=time.time()

n_old=['017','034','068']

num_list=set([str(i) for i in range(0,10)])

n_new=[]

p_list=[17,13,11,7,5,3,2]

x=102

while x<=1000:#generates a list for last 3 digits

    if len(str(x))==len(set(str(x))):

        n_old.append(str(x))

    x+=p_list[0]

for i in range(1,len(p_list)):#adds a number for each case by condition.

    for j in range(len(n_old)):

        candidates=num_list-set(n_old[j])

        for k in candidates:

            test=int(n_old[j][0:2])+int(k)*100

            if test % p_list[i]==0:

                n_new.append(k+n_old[j])

                continue

    n_old=n_new

    n_new=[]

for i in range(len(n_old)):#adds a number for foremost number except zero.

    k=num_list-set(n_old[i])

    k=k.pop()

    if k!='0':

        n_new.append(k+n_old[i])

print(sum([int(i) for i in n_new]))

et=time.time()

t=et-st

print("It takes %f secs to calculate, LOL." %t)

좀 기네요... 여하간 10ms에서 30ms 정도 걸립니다.