이번 문제는 100!의 모든 자리수 숫자들의 합을 구하는 것이다.
n! 이라는 표기법은 n × (n − 1) × … × 3 × 2 × 1을 뜻합니다.
예를 들자면 10! = 10 × 9 × … × 3 × 2 × 1 = 3628800 이 되는데,
여기서 10!의 각 자리수를 더해 보면 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 입니다.
100! 의 자리수를 모두 더하면 얼마입니까?”””
(http://euler.synap.co.kr/prob_detail.php?id=20)
접근
팩토리얼 함수는 이전 항에서 새로 추가된 다음 번 자연수를 곱해주면 되는 거라, 재귀적으로 작성할 수도 있는데, 그냥 1~n 까지의 모든 자연수를 곱하는 것이라 루프를 돌리거나, reduce()
를 써도 된다. 아래 구현은 reduce()
를 이용했다.
파이썬의 경우 100! 수준의 큰 수도 그닥 문제될 게 없기 때문에 (1000자리가 넘는 수도 거뜬히 계산할 수 있다.) 이런 작업은 일도 아니라 할 수 있다.
from functools import reduce
def factorial(n):
if n < 2:
return 1
return reduce(lambda x, y: x * y, range(1, n+1), 1)
def p20():
print(sum((int(x) for x in str(factorial(100))))
%time p20()
Swift 풀이
Swift는 이전의 큰 수 문제들에서 사용했던 BigNumber
를 사용한다.
func sovleP20() {
let x = (2...100).map{ BigNumber(integer: $0) } // 2~100 까지 BigNumber의 배열을 만들고
.reduce(BigNumber(integer: 1), *) // 모두 곱합니다.
.description // 그 결과를 문자열로 변환하고
.characters.flatMap{ Int(String($0)) } // 각 글자를 다시 정수로 변환,
.reduce(0, +) // 더합니다.
print(x)
}
참고
BigNumber
타입의 정의는 아래 Gist를 참고한다.