콘텐츠로 건너뛰기
Home » 오일러 프로젝트 38

오일러 프로젝트 38

수 192에 1, 2, 3을 각각 곱합니다.

\begin{align}
192 \times 1 &= 192 \\
192 \times 2 &= 384 \\
192 \times 3 &= 576
\end{align}

곱한 결과를 모두 이어보면 102384576이고, 이것은 1-9 팬디지털(pandigital) 수입니다. 이런 과정을 편의상 ‘곱해서 이어붙이기’라고 부르기로 합니다.

같은 식으로 9와 (1, 2, 3, 4, 5)를 곱해서 이어붙이면 918273645라는 1-9 팬디지털 수를 얻습니다. 어떤 정수와 (1, 2, 3, …, n)을 곱해서 이어붙였을 때 얻을 수 있는 가장 큰 아홉자리의 1-9 팬디지털 수는 무엇입니까? (단 n > 1)

https://euler.synap.co.kr/prob_detail.php?id=38

최대 범위를 찾는 것이 중요한데, n > 1 이니 최소한 1, 2를 곱해서 이어붙인 값이 1-9 팬디지털 수여야 한다. 5000 이상의 네 자리 수는 1을 곱하면 네 자리수를, 2를 곱하면 다섯 자리수를 만들기 때문에 팬디지털 곱셈식을 만들 수 있는 가능성이 있지만, 10000 이상의 수부터는 팬디지털 수를 만들 수 없다. 따라서 최대 범위는 9,999가 될 것이다.

“이어붙이기”를 수행하고 그 결과가 1-9 팬디지털 수인지 검사하는 함수를 작성해보자. bool 값으로 주기 보다는 조건을 만족하는 경우에는 만들어진 문자열을, 그렇지 않은 경우에는 빈 문자열을 리턴하도록 한다. (빈문자열은 if 구문에서 falsy하게 취급된다. 혹은 None을 리턴해도 같은 맥락으로 사용할 수 있다.

def test(n: int) -> str:
  s = ""
  for i in range(9):
    s += str(n * (i + 1))
    if len(s) >= 9:
      break
  if ''.join(sorted(s)) == '123456789':
    return s
  return ''

print(test(192))
# 192384576
print(test(9))
# 918273645

이렇게 만들어지는 값들 중에서 최대를 찾으면 된다. 주의할 것은 n이 크다고 해서 그 결과가 더 큰 것은 아니라는 것이다. (192와 9의 결과를 비교해도 알 수 있다.) 따라서 전수 검사한 결과를 찾으면 된다.

%time print(max(test(n) for n in range(1, 10000)))
# CPU time 15.6 ms