프로젝트 오일러 034

문제

34번 문제

각 자릿수의 팩토리얼을 더했을 때 자기 자신이 되는 수들의 합은?

사이냅소프트

접근

앞서 풀어본 바 있는 각 자리 수를 다섯제곱한 합과 원래의 수가 같아지는 문제와 비슷한 점이 많습니다. 여기서도 편의를 위해 각 자리 수의 팩토리얼의 합을 계산하는 연산을 '오렌지 따기'라고 부르겠습니다.

9!의 값은 362,880으로 7자리 수인 9,999,999에 대해 오렌지 따기한 결과는 362,880 × 7 = 2,549,160이 됩니다. 따라서 2,549,160보다 큰 수는 오렌지 따기한 결과가 자기 자신이 될 수 없습니다. 혹시 오렌지 따기의 결과가 자신과 같을 수 없는 최대치는 이 보다 더 작을 수도 있지 않을까요? 9가 많을수록 오렌지 따기의 값이 커지니, 이 값보다 작고 9가 가장 많은 2,499,999에 대해 오렌지 따기를 적용해 봅니다.

값은 1,814,426입니다. 다시 이 보다 작고 9가 최대로 많은 값은 1,799,777 이고 이 값을 오렌지따기하면 1,819,441입니다. 결국 이론상 낮출 수 있는 최대값은 1814426이 될 것 같습니다.

fs = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

def orange(n: int) -> int:
  ns = [int(x) for x in f'{n}']
  return sum(fs[n] for n in ns)

print(sum(x for x in range(1, 1819441) if oragne(x) == x))

참고로 이렇게 '특별한 수'는 '팩토리올'이라는 이름으로 부르고 있습니다. 약간 허무하게도 팩토리올은 4개 밖에 존재하지 않기 때문에, 검색만 해봐도 어떤 값이 있는지 금방 알 수 있습니다.