이번 문제는 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를 참고한다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 | |
| } |