[Project Euler] 52. Permuted multiples

1. 개요

    문제는 이곳에서 확인할 수 있다. \((x)\)를 양의 정수 \(x\)의 각 자리의 숫자라고 하자. \((x)=(2x)\)가 성립하는 \(x\) 중의 하나는 125874가 있다. \((x)=(2x)=(3x)=(4x)=(5x)=(6x)\)가 성립하는 최소 \(x\)를 찾는 것이 문제의 목표이다.  

2. 구현

    문제의 특성을 잘 살펴보면 확인해야 할 숫자를 많이 줄일 수 있다. 먼저 \((x)\) = \((6x)\)이므로 \(x\)는 반드시 1로 시작한다. 그렇지 않으면 자리수가 달리지기 때문이다. 또한 \(5x\)가 5의 배수이므로 마지막 수는 0 또는 5이다. 따라서 \((x)\)는 0 또는 5를 포함한다. 마찬가지로 \(2x\)가 2의 배수이므로 \((x)\)는 0, 2, 4, 6 또는 8을 포함한다. 또한 \(x\)는 3의 배수이다. 왜냐하면 \((3x)\)의 합이 3의 배수이며 \((x)=(3x)\)이기 때문이다.

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

i = 1

while True:

    # 3x가 3의 배수이고 x와 3x의 digit이 같으므로 x도 3의 배수이다.
    x = 3*i
    x_digit = sorted(list(map(int, str(x))))

    # 6x와 x의 digit이 같으므로 x는 1로 시작한다.
    # 5x가 5의 배수이므로 x는 0 또는 5를 포함한다.
    # 2x가 2의 배수이므로 x는 0, 2, 4, 6 또는 8을 9포함한다.
    if x_digit[0] != 1 or not any(d in [0, 5] for d in x_digit) or not any(d in [0, 2, 4, 6, 8] for d in x_digit):
        i += 1
        continue

    result = True

    for k in range(2, 7):
        result &= x_digit == sorted(list(map(int, str(k*x))))

    if result:
        print(x)
        break

    i += 1

    답은 142857이다.