[Project Euler] 43. Sub-string divisibility

1. 개요

  문제는 이곳에서 확인할 수 있다. 1406357289는 0부터 9까지의 수가 한번씩 등장하는 수(0 to 9 pandigital)이다. 그리고 \(d_n\)을 \(n\)번째 자리의 수라고 하면 이 숫자의 sub-string은 다음과 같은 특징이 있다.

• \(d_{2}d_{3}d_{4}=406\)은 2로 나누어 떨어진다.
• \(d_{3}d_{4}d_{5}=063\)은 3으로 나누어 떨어진다.
• \(d_{4}d_{5}d_{6}=635\)은 5로 나누어 떨어진다.
• \(d_{5}d_{6}d_{7}=357\)은 7로 나누어 떨어진다.
• \(d_{6}d_{7}d_{8}=572\)은 11로 나누어 떨어진다.
• \(d_{7}d_{8}d_{9}=728\)은 13으로 나누어 떨어진다.
• \(d_{8}d_{9}d_{10}=289\)은 17로 나누어 떨어진다.

  이와 같은 특징을 보이는 0 to 9 pandigital의 합을 구하는 것이 문제의 목표이다.

2. 구현

  0 to 9 pandigital을 찾기 위하여 재귀 함수를 사용한다.

# -*- coding: utf-8 -*-

import datetime as dt

answer = 0

def pandigital_number(current_digit = ''):
    
    if len(current_digit) > 0 and current_digit[0] == '0':
        return
    
    if len(current_digit) == 10:
        
        for idx, p in enumerate([2, 3, 5, 7, 11, 13, 17]):
            
            if int(current_digit[idx+1:idx+4]) % p != 0:
                return
        else:
            print(current_digit)    
            global answer
            answer += int(current_digit)
            return 
    
    left_digit = [str(s) for s in range(0,10) if str(s) not in current_digit]
    
    for s in left_digit:
        
        pandigital_number(current_digit + s)

print('START AT ', dt.datetime.now().strftime('%Y-%m-%d %H:%M:%S'))
pandigital_number()    
print('FINISH AT ', dt.datetime.now().strftime('%Y-%m-%d %H:%M:%S'))
print(answer) 

답은 16695334890이다.