오일러 프로젝트 20

이번 문제는 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를 참고한다.