Wireframe

오일러 프로젝트 52

125874를 2배하면 251748이 되는데, 이 둘은 같은 숫자로 이루어져 있고, 순서만 다릅니다. 2배, 3배, 4배, 5배, 6배의 결과도 같은 숫자로 이루어지는 가장 작은 수는 무엇입니까?

http://euler.synap.co.kr/prob_detail.php?id=51

접근

프로젝트 오일러의 문제들 중에는 같은 숫자들이 순서만 다른, 즉 같은 숫자들의 순열인 값들에 대한 문제가 종종 나온다. 같은 숫자들의 순열인 값들은 흥미롭게도 그 차이가 9의 배수가 된다는 것이다.

두 자리 숫자 “AB”는 A * 10 + B 로 표현할 수 있는데, 순서를 바꾼 10 * B + A 와의 차이를 보면 결국 9 * A – 9 * B 가 된다. 세자리, 네자리수에서도 비슷하게 10의 거듭제곱만큼 차이가 있으니 차이는 모든 숫자의 차이는 9의 배수가 되고 그 차이의 합 역시 9의 배수가 된다.

어떤 수를 2배, 3배, 4배 한다는 것은 그 배수들의 차이가 자기 자신이라는 말로, 즉 문제의 조건을 만족하는 모든 수는 9의 배수라는 점을 알 수 있다. 그 외에 숫자들의 구성에서도 제약 사항이 있을까? 우선 6배 할 때까지 같은 순열이 되려면 숫자의 개수가 변하지 않아야 한다. 따라서 앞부분의 숫자가 적당히 작은 값이어야 한다. 6배 했을 때까지 자리수가 변하지 않으려면 12, 13, 14, 15, 16 중 하나로 시작해야 한다. (11은 두 배하면 22가 돼버림)

그리고 끝자리를 생각해보자. 2배, 3배, …, 6배 하는 동안 끝자리 숫자가 어떻게 변할까?

즉 1로 시작하고 7로 끝나는 9의 배수인 6자리 수에서 이 조합이 나오게 될 것이다. 각 순열을 정수로 변환하고, 이를 2~6배한 각각의 수가 모두 같은 순열인지를 검사한다. 순열 검사는 각 자리 수로 분해한 후 정렬하는 방법을 사용하기 때문에 결국 숫자를 각 자리 숫자의 튜플로 만들거나, 그 역변환을 수행하는 digits(), dump() 함수를 정의하여 사용하였다.

찾는 범위를 극도로 줄였기에 수행시간은 매우 짧다.

from functools import reduce
from collections import Counter

dump = lambda xs: reduce(lambda x, y: x * 10 + y, xs)
digits = lambda n: tuple(map(int, str(n)))

def perm_dups(xs, n):
  def helper(acc, cnts, n):
    if n == 0:
      yield acc
      return
    for k, v in cnts.items():
      yield from helper((*acc, k), {**cnts, k:v-1}, n-1)
  yield from helper((), Counter(xs), n)

ds = list(range(10)) * 6

for ds in perm_dups(ds):  # 7을 일부러 맨 뒤에 넣음
  if ds[0] == 0 or ds[0] > 1 or ds[1] > 6:
    continue
  n = dump(ds)
  if d % 9 > 0:
    continue
  m = dump(sorted(digits(n)))
  if all(m == dump(sorted(digits(n * i))) for i in range(2, 7)):
    print(n)
    break

# 142857
# CPU Times: total 125 ms

Exit mobile version