오일러 프로젝트 34 번 문제는 어떤 수를 각자리 숫자로 나누고, 각 자리 숫자들의 팩토리얼 값의 합계를 계산했을 때 원래 값이 되는 것들을 찾는 문제이다.
숫자 145에는 신기한 성질이 있습니다. 각 자릿수의 팩토리얼(계승)을 더하면 1! + 4! + 5! = 1 + 24 + 120 = 145 처럼 자기 자신이 됩니다. 이렇게 각 자릿수의 팩토리얼을 더하면 자기 자신이 되는 모든 수의 합을 구하세요. 단, 1! = 1 과 2! = 2 의 경우는 덧셈이 아니므로 제외합니다.
http://euler.synap.co.kr/prob_detail.php?id=34
접근
한자리 수의 팩토리얼 중 가장 큰 값인 9!은 362880이므로 문제에서 말하는 식으로 처리했을 때, 6자리 미만인 경우에는 최대 6자리 혹은 7자리의 값이 나올 수 있다. 999,999의 경우 이렇게 처리하면 2백만이 조금 넘는 값이 나오고 일곱자리 수의 경우에도 최대 250만 근처의 값이 나온다. 따라서 검사해야 하는 범위는 9!*7까지의 값 되겠다.
참고로 0! 은 1로 취급한다.
성능 향상을 위한 고민
가장 나이브한 팩토리얼 계산은 재귀를 사용하는 것이고, 보다 개선된 계산법은 2~ n까지의 값을 모두 곱하는 (reduce()!) 것이다. 그런데 여기서는 0~9 의 팩토리얼 값만 필요하므로, 그냥 상수값으로 넣고 인자로 꺼내쓰는게 가장 빠르다.
1자리 숫자의 팩토리얼 계산을 가장 빨리할 수 있는 방법은 계산된 결과를 리스트에 넣고 인자로 꺼내는 방법이다.
범위 줄이기
250만번 루프를 도는 것이 만만한 작업이 아니다. 사실 파이썬에서는 백만번 루프를 돈다고 생각하면 수 초가 소요되는 것은 기본이다. 이 문제를 풀어보고 나면 답은 생각보다 작고 실질적으로는 10만 미만에서만 해당 조건을 만족하는 값들이 분포함을 알 수 있다. 하지만 실제로 이 한계값은 약 150만수준까지만 내려볼 수 있다.
FACTORIALS = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
def factorial(n):
return FACTORIALS[n]
def process(n):
return n == sum((factorial(int(x)) for x in str(n)))
def e034():
print(sum([x for x in range(10, 2540160+1) if process(x)]))
%time e034()
# Wall time: 14.7 s
Swift 풀이
기왕 파이썬 풀이에서 답은 얻었겠다. 범위는 좀 좁혀서 계산해보는 것으로 했다.
func test(_ n: Int) -> Bool {
let fs = [1,1,2,6,24,120,720,5040,40320,362880]
var (k, x) = (n, 0)
while k > 0 {
x += fs[k % 10]
k /= 10
}
return x == n
}
print((10...2_500_000).filter(test).reduce(0, +))정리
합계가 아닌 리스트 자체를 구해보면 달랑 4개의 숫자만 이 조건을 만족한다는 것을 알 수 있다. 이 네 개의 숫자를 특별히 팩토리올(factoriols)이라 부른다 하더라…