열 세번째 문제. 이번 문제는 “아주 큰 수들의 덧셈”이다.
아래에 50자리 숫자가 100개 있습니다. 이것을 모두 더한 값의 첫 10자리는 얼마입니까? (http://euler.synap.co.kr/prob_detail.php?id=13)
37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 .... 20849603980134001723930671666823555245252804609722 53503534226472524250874054075591789781264330331690
접근
사실 이 문제는 파이썬 같은 문제에는 별로 어울리지 않는다. 왜냐하면 파이썬, 하스켈과 같은 일부 언어에서는 정수의 크기에 제한이 없기 때문이다. 따라서 파이썬에서는 사실 다음과 같이 처리하면 된다.
s = "37107287533902102798797998220837590246510135740250\n46376937677490009712648124896970078050417018260538...."
print(str(sum(int(x) for x in s.split()))[:10])문제는 정수 타입의 크기에 제한이 있는 언어들이다. 예를 들어 Swift의 부호없는 정수인 UInt 타입은 64비트이므로 약 20자리의 정수까지를 담을 수 있다. (최대 18,446,744,073,709,551,615) 따라서 50자리 정수의 덧셈을 계산하는 것은 기존의 타입으로는 불가능하다. 따라서 더 큰 정수의 덧셈을 할 수 있는 별도의 타입을 만들어서 계산해야 한다.
덧셈의 원리
10진수 두 개를 더하는 경우를 생각해보자. 36 + 84 를 예로 들어보겠다. 이를 우리가 손으로 더하여 계산하는 과정은 다음과 같이 처리된다.
- 각 두 수의 1의 자리 수를 더한다. (6 + 4)
- 1의 결과에서 1의 자리 수를 남겨두고, 10의 자리 수는 위로 올린다.
- 10의 자리 수 (6+4에서 올라온 1을 포함) 3개를 더한다.
- 결과는 120이 된다.
하나의 10진수를 10을 기준으로 하는 다항식으로 전개하여 표현한다면 아래와 같을 것이다.
만약 50자리 정수를 처리한다고 하면 이와 같은 식으로 처리할 수 있을 것이다. 먼저 10^0 에 해당하는 숫자를 더한 후, 이를 10으로 나눠 몫은 위쪽 레벨로 올려주고, 나머지를 취하여 10^0 자리의 숫자로 사용한다. 그러면서 10^1, 10^2 자리에 대해서 각각 같은 처리를 수행한다. 긴 정수를 이렇게 다항식으로 본다면 50자리 정수는 50항짜리 식으로 변환하고, 각 계수들을 이어 붙여서 숫자를 표기하면 되는 것이다.
이 로직을 이용해서 문제를 다음과 같이 풀면 된다.
- 100개의 50자리 숫자를 모두 분해하여 정수 리스트로 만든다. (그리드로 사용할 것이다.)
- 49번째 열의 모든 정수들을 합한다. 이 합을 10으로 나눈 나머지가 1의 자리 숫자가 될 것이고, 10으로 나눈 몫은 윗자리 계산에 포함될 것이다.
- 48번째 열의 모든 정수와, 이전 계산에서 올려진 값을 모두 합친다. 이후에는 계속 10으로 나눈 나머지를 기록하고, 10으로 남은 몫을 위로 올린다.
- 3의 과정을 0번째 열까지 반복한다.
- 모든 열을 더하고 남은 플래그값에는 숫자가 남아있을 수 있다. 이 값의 각 자리 수를 기록한다.
- 최종 결과를 역으로 뒤집어 붙인다.
아래는 이에 대한 Swift 4 풀이이다. (숫자가 너무 길어서 생략했다. 전체 코드는 여기서 확인할 수 있다.)
let s = """
37107287533902102798797998220837590246510135740250
...
53503534226472524250874054075591789781264330331690
"""
let d = s.characters.flatMap{ Int(String($0)) } // flatMap을 이용해서 맵핑하면, 숫자로 변환할 수 없는 항은 무시된다.
var result = Array<Int>()
var flag: Int = 0
for i in stride(from: 49, through: 0, by: -1) { // 50개 열에 대해 각각의 자리수끼리를 더한다.
let x = (0..<100).map{ d[$0 * 50 + i] }.reduce(0, +) + flag
result.append(x % 10)
flag = x / 10
}
// 모든 열을 더 한 후, 올려진 값의 각 자리를 추출
while flag > 0 {
result.append(flag % 10)
flag /= 10
}
// 최종 결과 출력
print(result.reversed().map{ String($0) }[0..<10].joined(separator: ""))이 아이디어를 확장해서 큰 정수를 표현하는 타입을 새롭게 만드는 것도 가능하다. 굳이 10단위로 쪼개지 않고 1000, 10000 단위 등으로 쪼개어 사용하면 더 적은 컨테이너를 사용해서 연산 절차를 간소하게 만들 수 있을 것이다. 추후에 큰 정수를 곱해야 하는 문제가 있으니, 그 때 큰 정수를 다루는 방법에 대해서 좀 더 살펴보도록하겠다.