오일러 프로젝트 34

수 145는 신기한 성질이 있습니다. 각 자릿수의 팩토리얼(계승)을 더하면 1! + 4! + 5! = 1 + 24 + 120 = 145 처럼 자기 자신이 됩니다. 이렇게 각 자릿수의 팩토리얼을 더하면 자기 자신이 되는 모든 수의 합을 구하세요.

단, 1! = 1, 2! = 2 의 경우는 덧셈이 아니므로 제외합니다.

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

9! = 362,880이며, 모든 자리가 9로 구성된 수들의 팩토리얼의 합은 이 값의 배수가 된다. 이 값의 배수는 4자리부터 9자리까지 모두 7자리 수의 값이 되므로, 7자리를 넘어가는 수는 각 자릿수의 팩토리얼 합이 자신이 될 수 없게 된다. 7자리 수에서도 2540160이 최대값이므로, 검사해야 하는 한계값이 이 값이 될 것이다.

팩토리얼을 계산해야 하는 수는 고작 10개 밖에 없으니 매번 계산하기 보다 계산해놓은 결과를 튜플에 기록해놓고 계산하면 수행 시간을 단축하는데 도움이 될 것이다.

fs = (1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880)

def test(n):
    ns = sum(fs[i] for i in map(int, str(n)))
    return ns == n

res = sum(filter(test, range(10, 362880 * 7)))
print(res)

250만 번 가량의 루프를 돌아야하지만, filter()를 사용하면 그나마 파이썬 루프의 오버헤드가 많이 줄어들기 때문에 몇 초 수준에서 답을 낼 수 있습니다.