오일러 프로젝트 62

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

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

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

접근

예를 들어 7자리 수가 하나 있다고 하면 그 순열의 가지수는 7!로 5040개나 된다. 그 중에서 세제곱수를 다섯개 찾아보고 다른 조합에서 이를 반복한다? 이 방법으로는 시간이 너무 오래 걸릴 것이다. 그리고 문제는 답이 몇 자리 수에서 나올지도 알 수 없다는 것이다. 따라서 오직 세제곱수만 생각해보기로 하자. 2자리 세제곱수는 2개 밖에 없으며, 3자리 세제곱수는 5개 밖에 없을 정도로 세제곱수는 드물다. 10¹⁰ 의 세제곱수는 30자리 수인데, 0~9가 3번씩 고르게 사용되어 순열의 수가 가장 많을 때에는 무려 4,420,880,996,869,850,977,271,808,000,000 개나 되므로 이 범위에서는 충분히 찾고 넘칠 것이다. 그리고 조건을 만족하는 최소값을 찾는 시점에 중단할 것이기 때문에, 최대 범위는 얼마나 크든지 상관없다.

각 세제곱수에 대해서 같은 순열로 묶기 위해서는 각 숫자를 순서대로 정렬한 값을 키로 하여, 리스트에 추가한다. 이런식으로 같은 순열에서 세제곱수 5개가 모이는 시점에 탐색을 중단한다.

%%time
table: dict[tuple[int, ...], list[int]] = dict()
for i in range(1, 10**10):
  j = i**3
  k = tuple(sorted(map(int, str(n)))
  table.setdefault(k, []).append(k)
  if len(table[k]) == 5:
    print(table[k][0])
    break

전체 수행시간은 대략 15~30 ms 소요된다.