오일러프로젝트 13

37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
....
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690

접근

보통의 프로그래밍 언어에서 정수 타입은 그 크기가 고정되어 있어서 표현할 수 있는 정수값의 범위에 제한이 있다. 통상 64비트 정수의 경우 2진수 64자리이며, 이를 십진수로 환산하면 약 20자리 정도 밖에 되지 않는다. (부호없는 64비트 정수의 가장 큰 값은 18,446,744,073,709,551,616이다.)

따라서 큰 정수의 경우에는 다항식을 표현하는 기법등을 사용해서 덧셈이나 곱셈등을 지원하는 별도의 타입을 구현해야 한다. 하지만 파이썬의 정수는 기본적으로 ‘큰 정수’이며 실질적인 자리수에 한계는 없다. (대신에 자리수가 아주 많아지면 연산이 그만큼 오래 걸린다.)

가장 간단하게는 주어진 문자열을 개행문자 기준으로 자른 다음, 정수형으로 변환하고 모두 더한다. 앞에서부터 10자리는 문자열로 변환한 후 앞 10글자를 얻으면 된다.

# 숫자는 편의상 줄여서 씀
s = """37107287533902102798797998220837590246510135740250
46376937677490009712648..."""
print(str(sum(map(int, s.splitlines())))[:10])

큰 수의 덧셈을 구현하기

큰 수의 덧셈을 간단한 함수를 사용해서 구현해보자. 먼저 숫자로된 문자열을 각 자리 수의 배열로 만들거나, 그 반대의 연산을 수행하는 두 개의 변환함수 parse(), compose() 를 아래와 같이 정의할 수 있다. 문자 ‘0’ 의 아스키코드 값이 48이기 때문에 숫자의 아스키코드에서 48을 빼면 실제 숫자가 표현하는 정수값을 얻을 수 있다.

parse = lambda s: [ord(x) - 48 for x in s]
compose = lambda xs: "".join(chr(x + 48) for x in xs

이 함수들을 이용해서 두 개의 긴 숫자 문자열에 대해서 덧셈을 수행하는 함수를 작성해볼 것이다. 함수의 알고리듬은 우리가 덧셈을 손으로 계산하는 것과 동일하다. 두 문자열의 길이를 큰 쪽으로 맞춘 후 parse() 함수를 사용해서 한자리 정수의 리스트로 변환한다. 그런 다음 아래쪽 자리부터 두 개의 정수를 더하고 그 결과를 이어 붙인다. 이 때 주의할 것은 그 합이 9보다 큰 경우에는 10이 올라가는 값을 잘 처리해줘야 한다는 것이다.

def s_add(a:str, b:str) -> str:
  l = max(len(a), len(b))
  a = parse(a.zfill(l))[::-1]
  b = parse(b.zfill(l))[::-1]
  res = []
  z = 0
  for (x, y) in zip(a, b):
    z, w = divmod(x + y + z, 10)
    res.append(w)
  if z > 0:
    res.append(z)
  return compose(res[::-1])

# 테스트
s_add('123', '898')
# > '1021'

이 함수를 사용해서 주어진 문자열을 행 단위로 끊은 다음 하나로 접으면 덧셈이 완성된다.

from functools import reduce

s = "..."

print(reduce(s_add, s.splitlines())[:10])