오일러프로젝트 013

열 세번째 문제. 이번 문제는 “아주 큰 수들의 덧셈”이다.

아래에 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. 각 두 수의 1의 자리 수를 더한다.  (6 + 4)
  2. 1의 결과에서 1의 자리 수를 남겨두고, 10의 자리 수는 위로 올린다.
  3. 10의 자리 수 (6+4에서 올라온 1을 포함) 3개를 더한다.
  4. 결과는 120이 된다.

하나의 10진수를 10을 기준으로 하는 다항식으로 전개하여 표현한다면 아래와 같을 것이다.

만약 50자리 정수를 처리한다고 하면 이와 같은 식으로 처리할 수 있을 것이다.  먼저 10^0 에 해당하는 숫자를 더한 후, 이를 10으로 나눠 몫은 위쪽 레벨로 올려주고, 나머지를 취하여 10^0 자리의 숫자로 사용한다. 그러면서 10^1, 10^2 자리에 대해서 각각 같은 처리를 수행한다. 긴 정수를 이렇게 다항식으로 본다면 50자리 정수는 50항짜리 식으로 변환하고, 각 계수들을 이어 붙여서 숫자를 표기하면 되는 것이다.

이 로직을 이용해서 문제를 다음과 같이 풀면 된다.

  1. 100개의 50자리 숫자를 모두 분해하여 정수 리스트로 만든다. (그리드로 사용할 것이다.)
  2. 49번째 열의 모든 정수들을 합한다. 이 합을 10으로 나눈 나머지가 1의 자리 숫자가 될 것이고, 10으로 나눈 몫은 윗자리 계산에 포함될 것이다.
  3. 48번째 열의 모든 정수와, 이전 계산에서 올려진 값을 모두 합친다. 이후에는 계속 10으로 나눈 나머지를 기록하고, 10으로 남은 몫을 위로 올린다.
  4. 3의 과정을 0번째 열까지 반복한다.
  5. 모든 열을 더하고 남은 플래그값에는 숫자가 남아있을 수 있다. 이 값의 각 자리 수를 기록한다.
  6. 최종 결과를 역으로 뒤집어 붙인다.

아래는 이에 대한 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 단위 등으로 쪼개어 사용하면 더 적은 컨테이너를 사용해서 연산 절차를 간소하게 만들 수 있을 것이다.  추후에 큰 정수를 곱해야 하는 문제가 있으니, 그 때 큰 정수를 다루는 방법에 대해서 좀 더 살펴보도록하겠다.