오일러 프로젝트 62

세제곱수인 41063625(=345³)로 순열을 만들어 보면 그 중에서 56623104(=384³)와 66430125(=405³)가 또 세제곱수입니다. 실제 41063625는, 자릿수로 만든 순열 중에서 3개가 세제곱수인 가장 작은 수입니다.

그러면 자릿수로 만든 순열 중에서 5개가 세제곱수인 가장 작은 숫자는 무엇입니까?

https://euler.synap.co.kr/problem=62

접근

문제에서는 7자리 수를 예로 들고 있다. 임의의 일곱자리 수 A를 하나 선택하고, 이 와 같은 순열을 모두 찾으면 7!(5040)개를 찾을 수 있고, 이 중에서 세제곱수를 찾아 다섯개가 되는 경우를 찾으면 어떨까? 일단 문제의 답이 7자리라는 보장도 없고 이 과정에서 찾아봐야 하는 수는 너무 많다. (900만개 정도의 수에 대해서 세제곱수인지 검사를 해야 한다)

따라서 세제곱수 자체에만 집중해보도록 하자. 두 자리 자연수 중에 세제곱수는 27과 64 두 개 밖에 없으며, 세자리 세제곱수는 5개 밖에 없을 정도로 세제곱수는 드물게 분포하고 있다. 따라서 자연수의 세제곱수들을 그 각각의 최소순열을 기준으로 그룹지으면, 같은 순열인 수들로 묶을 수 있다. 어떤 자연수 k를 1씩 늘려가면서 그 세제곱수의 최소순열에 대해서 추가하고, 최소순열 당 연결된 세제곱수가 5개가 되는 값을 찾으면 된다. 그 시점이 가장 작은 세제곱수를 5개 만드는 순열이 될 것이다.

풀이

%%time
k = 345
cache: dict[str, list[int]] = {}
while True:
  j = k**3
  key = ''.join(sorted(str(j)))
  cache.setdefault(key, []).append(j)
  if len(cache[key]) == 5:
    print(min(cache[key]))
    break

# 127035954683
# elapsed: 0.000 ms

그 값이 크기는 하지만 세제곱수의 분포가 제법 드물다는 것을 생각하면 굉장히 빠르게 문제를 해결할 수 있다.