38. Pandigital multiples

1. 개요

  문제는 이곳에서 확인할 수 있다. 192를 1, 2 그리고 3과 곱하면 각각 192, 384, 567이고 이 숫자들을 순서대로 연결하면 192384567이 된다. 192384567는 1부터 9까지의 숫자가 한번씩만 나오는 pandigital이며 이 숫자를 192, (1,2,3)으로 표현하자. 이와 같은 방식으로 918273645는 9, (1,2,3,4,5)로 표현할 수 있다. 1부터 9까지의 pandigital 중에 \(x\), \((1,2,\dots, n)\)으로 표현할 수 있는 가장 큰 수를 구하는 것이 목표이다. 단, \(n>1\)이다.

2. 구현

  \(x\)에는 하한선과 상한선이 존재한다. 하한선은 1이며, \(n\)은 1보다 큰 정수이므로 상한선은 4자리 숫자이다.

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

max_pandigital = 0

for x in range(1, 9999):
    pandigital_candidate, i = '', 1

    while len(pandigital_candidate) < 9:
        pandigital_candidate += str(i * x)
        i += 1

    digit_set = set(pandigital_candidate)
    if len(pandigital_candidate) != 9 or len(digit_set) != 9 or '0' in digit_set:
        continue

    print('PANDIGITAL FOUND: {pandigital}, {x}, {integers}'.format(
        pandigital=pandigital_candidate, x=x, integers=list((range(1, i)))))

    max_pandigital = max(max_pandigital, int(pandigital_candidate))

print('ANSWER: {answer}'.format(answer=max_pandigital))

답은 932718654이다.