이번 문제는 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 | |
} |