오일러 프로젝트 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를 참고한다.

import Foundation
// 큰 수 덧셈과 곱셈은 특정 단위의 다항식처럼 처리한다.
/*: 큰 수를 다항식처럼 다룰 때, 하나의 항을 표현하는 타입.
각 항은 0~9999999999 까지의 값을 가지며, 차수를 나타내는 값을 별도로 가지고 있다.
*/
struct Node {
static let unitSize = 10000_00000
let level : Int
let value : Int
init(value: Int, level: Int = 0) {
self.value = value
self.level = level
}
func multiply(_ other: Node) -> [Node] {
// 두 항의 곱의 결과의 차수는 두 항의 차수의 합과 같다.
let level = self.level + other.level
var value = self.value * other.value
var upFlag = 0
if value >= Node.unitSize {
upFlag = value / Node.unitSize
value = value % Node.unitSize
}
if upFlag > 0 {
return [Node(value: upFlag, level: level + 1), Node(value: value, level: level)]
}
return [Node(value: value, level: level)]
}
}
struct BigNumber {
var nodes: [Node]
init(integer value: Int) {
var nodes: [Node] = []
var value = value
var level = 0
while value > 0 {
let v = value % Node.unitSize
nodes.append(Node(value: v, level: level))
level += 1
value = value / Node.unitSize
}
self.nodes = nodes
}
init(string str: String) {
let nodeLength = Int(log10(Double(Node.unitSize)))
var level = 0
var tempNodes:[Node] = []
while true {
var startPos = str.count – nodeLength * (level + 1)
// 마디의 시작위치가 0보다 작아서는 안된다.
let endPos: Int = (startPos < 0) ? str.count % nodeLength : nodeLength
startPos = startPos < 0 ? 0 : startPos
let startIndex = str.index(str.startIndex, offsetBy: startPos)
let endIndex = str.index(startIndex, offsetBy: endPos)
// 마디 끊기
let p = str[startIndex..<endIndex]
if let n = Int(p) {
tempNodes.append(Node(value: n, level: level))
level += 1
}
if startPos == 0 {
break
}
}
self.nodes = tempNodes
}
init(nodes: [Node]) {
var tempNodes: [Node] = []
let maxLevel = nodes.map{ $0.level }.max() ?? 0
var upFlag = 0
// 각 레벨의 노드에 대해서 계수의 합을 구한다.
for level in 0…maxLevel {
var value = nodes.filter{ $0.level == level }.map{ $0.value }
.reduce(0, +) + upFlag
if value >= Node.unitSize {
upFlag = value / Node.unitSize
value = value % Node.unitSize
} else { // 이 부분이 중요하다. 올림이 발생하지 않았다면, 올려진 값은 소진되었으므로 0으로 초기화한다.
upFlag = 0
}
tempNodes.append(Node(value: value, level: level))
}
// 모든 항을 처리한 후 올림이 남았는지 확인
if upFlag > 0 {
tempNodes.append(Node(value:upFlag, level: maxLevel + 1))
}
self.nodes = tempNodes
}
static func + (left: BigNumber, right: BigNumber) -> BigNumber {
// 덧셈은 두 다항식의 항을 모두 합쳐서 정리해버리면 끝!
return BigNumber(nodes: left.nodes + right.nodes)
}
func multiply(with node: Node) -> [Node] {
return self.nodes.flatMap{ $0.multiply(node) }
}
static func * (left: BigNumber, right: BigNumber) -> BigNumber {
let tempNodes = right.nodes.flatMap{ left.multiply(with: $0) }
return BigNumber(nodes: tempNodes)
}
static func * (left: BigNumber, right: Int) -> BigNumber {
return left * BigNumber(integer: right)
}
}
extension BigNumber: CustomStringConvertible {
var description: String {
var xs = nodes.sorted{ $0.level > $1.level }
let x = xs.removeFirst().value
let heading = x > 0 ? "\(x)" : ""
if !xs.isEmpty {
let remains: String = xs.map{
let padding = Int(log10(Double(Node.unitSize))) – ( $0.value == 0 ? 0 : Int(log10(Double($0.value))) + 1)
return String(repeating:"0", count:padding) + "\($0.value)"
}.joined(separator: "")
return heading + remains
}
return heading
}
}
func pow(_ a: BigNumber, _ b: Int) -> BigNumber {
if b == 0 { return BigNumber(integer: 1) }
let r = pow(a, b / 2)
if b % 2 == 0 {
return r * r
}
return r * r * a
}

view raw
BigNumber.swift
hosted with ❤ by GitHub