project euler

프로젝트 오일러 013

sooop

2024년 11월 2일 — 3 min read

Photo by Possessed Photography / Unsplash

문제

큰 수의 덧셈

50자리 10진수 중에서 가장 큰 9999....9999 (9가 50개) 2진수로 표현하면 166자리가 됩니다. 즉 166비트짜리 값입니다만, 이를 하나의 단위로 다룰 수 있는 컴퓨터는 없거나 흔치 않을 겁니다.

하지만 컴퓨터가 큰 수를 다루지 못하는 것은 아닙니다. 본질적으로 모든 진법에서 수는 각 자리와 그 자리를 표시하는 숫자로 작성되는 다항식입니다. 231 = 2×100 + 3×10 + 1이죠. 따라서 50자리 수는 50항짜리 다항식으로 생각할 수 있는데, 다항식에서는 차수가 같은 항의 계수끼리 더하면 된다는 사실을 이용하면 큰 수의 덧셈 문제를 풀 수 있습니다.

물론, 파이썬에서는 이런 원리를 사용해서 기본적으로 긴 수를 더할 수 있습니다. 그냥 하면 좀 성의가 없어보이니깐, 문제 페이지에서 값을 가져와서 풀어봐야겠죠.

import re
from urllib.request import urlopen


url = 'https://euler.synap.co.kr/problem=13'
res = urlopen(url)
t = res.read().decode()

mx = [int(x) for x in re.findall(r'\d{50}', t)]
print(str(sum(mx))[:10])

큰 수의 덧셈 구현해보기

큰 수의 덧셈을 실제로 구현해보면 아래와 같습니다. 그냥 보여주기 식이라서 그냥 성능은 크게 신경쓰지 않았어요. 그리고 괜히 숫자를 정수로 변환하는 데 int() 함수를 쓰는 것이 반칙 같다는 느낌이 들어서, 그 부분도 일부러 돌아가게 작성했습니다.

import re
from functools import reduce
from urllib.request import urlopen


url = 'https://euler.synap.co.kr/problem=13'
temp = urlopen(url)
t = temp.read().decode()
ts = re.findall(r'\d{50}', t)

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

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

print(reduce(s_add, ts)[:10])