오일러 프로젝트 16

2¹⁵ = 32768 의 각 자리수를 더하면 3 + 2 + 7 + 6 + 8 = 26 입니다. 2¹⁰⁰⁰의 각 자리수를 모두 더하면 얼마입니까?

http://euler.synap.co.kr/prob_detail.php?id=16

접근

이 문제는 13번처럼 큰 정수를 다룰 수 있는지를 확인하는 문제이다. 사실 같은 수끼리 더하면 두 배가 되므로, “1” 부터 시작해서 s_add() 함수에 같은 값을 두 번 넣어서 두 배하는 동작을 1,000번 하면 간단히 해결된다.

파이썬은 큰 정수를 지원하므로 2의 1000 제곱을 계산해서 문자열로 바꾼 후, 다시 각 숫자를 정수로 바꿔서 합산한다.

sum(map(int, str(2**1000)))
# 1366

어떤 수를 두 배 하는 것은 같은 수 두 개를 더하는 것과 같으므로, 문자열로 큰 수를 더할 수 있는 s_add() 함수를 사용해서 아래와 같이 풀어도 된다.

_parse = lambda s: [int(c) for c in s[::-1]]
_comps = lambda xs: ''.join(chr(x + 48) for x in xs[::-1])

def s_add(*args: str) -> str:
  l = max(map(len, args))
  xs = list(map(_parse, (x.zfill(l) for x in args)))
  temp, z = [], 0
  for ws in zip(*xs):
    z, w = divmod(sum(ws) + z, 10)
    temp.append(w)
  if z:
    temp.append(z)
  return _comps(temp)


a = "1"
for _ in range(1000):
  a = s_add(a, a)

print(sum(map(int, a)))

문자열을 이용한 큰 정수의 곱셈

문자열을 이용해서 큰 정수의 덧셈을 구현한 s_add()와 비슷하게 s_multi() 함수를 작성하고, 이를 이용해서 거듭제곱을 계산하는 s_power() 함수를 구현해보자.

곱셈을 구현하는 것도 그리 어렵지 않다. A x B 를 계산할 때, B의 각 자리 숫자를 b1, b2, b3, … bn 이라 하면 A * bn, A * b1 * 10, A * b2 * 100… 을 각각 문자열로 계산한 다음, s_add() 함수를 이용해서 이들을 모두 더하면 결과를 얻을 수 있다.

def s_multi(a: str, b: str) -> str:
  res: list[str] = []
  a, b = map(_parse, (a, b))
  for lv, y in enumerate(b):
    temp = [0] * lv  # 자리수에 맞게 0을 추가해줌
    z = 0
    for x in a:
      z, w = divmod(x * y + z, 10)
      temp.append(w)
    if z > 0:
      temp.append(z)
    res.append(_comps(temp))
  return s_add(*res)


# 제곱을 이용한 pow 함수

def s_pow(a: str, b: str|int) -> str:
  if isintance(b, str):
    b = int(b)
  if b == 0:
    return "1"
  if b == 1:
    return a
  # a의 (b /2) 제곱을 계산하고 이를 제곱한다.
  # 이렇게하여 반복주기를 줄인다.
  r = s_pow(a, b // 2)
  if b % 2 == 0:
    return s_multi(r, r)
  return s_multi(s_multi(r, r), a)

print(sum)map(int, s_power("2", 1000))))
# 1366