프로젝트 오일러 020

문제

20번 문제

100! 의 자릿수를 모두 더하면?

사이냅소프트

이번 문제 역시 큰 수와 관련된 내용이고, 100!는 파이썬으로 구할 수 있는 범위의 수이므로 그대로 구해보면 됩니다.

def factorial(n):
  if n < 2:
    return 1
  s = 1
  for i in range(n):
    s *= (i + 1)
  return s

print(sum(map(int, str(factorial(100)))))

큰 수의 곱셈 구현하기

사실 파이썬에서 파이썬으로 큰 수의 연산을 구현해봐야, 파이썬이 원래 제공하는 큰 정수 연산보다 더 나은 성능을 만들 수는 없습니다. 그래도 출제자의 의도가 큰 수의 곱셈을 생각하고 있는 문제이니, 한 번 구현해보도록 하겠습니다. 코드를 작성하기 전에 몇 가지 가정을 하고, 그에 맞춰서 구현하는 것이 좋을 듯 합니다.

1. 문자열은 각 자리의 정수의 리스트로 변환한 후 계산합니다. 그리고 이후에 계산된 결과를 다시 문자열로 변환합니다. 따라서 실제 연산 로직은 정수의 리스트를 큰 수로 취급하여 정수의 리스트를 리턴하는 함수가 됩니다.
2. 작은 자리 숫자부터 먼저 처리합니다.
3. 곱셈의 구현을 좀 더 편하고, 빠르게 하기 위해서 덧셈은 2개 이상의 인자를 받아서 한꺼번에 처리할 수 있도록 합니다.

코드는 아래와 같습니다. 함수 s_add(), s_multi()는 각각 정수의 리스트로 변환된 큰 수의 정보를 이용해서 덧셈과 곱셈을 수행합니다. add(), multi() 함수는 사실 문자열을 정수의 리스트로 변환한 다음, 각각 s_add(), s_multi()에 넘겨서 연산하고 다시 그 결과를 문자열로 바꿔 리턴합니다.

def parse(s: str) -> list[int]:
    return [ord(x) - 48 for x in s][::-1]


def dump(xs: list[int]) -> str:
    return "".join(chr(x + 48) for x in xs[::-1])


def s_add(*xs: list[int]):
    w = max(map(len, xs))
    temp = [0] * (w * len(xs))
    res = []
    for i, x in enumerate(xs):
        temp[i * w : i * w + len(x)] = x[:]
    f = 0
    for i in range(w):
        f, s = divmod(sum(temp[i::w]) + f, 10)
        res.append(s)
    if f > 0:
        res.append(f)
    return res


def s_multi(a: list[int], b: list[int]) -> list[int]:
    res = []
    for i, x in enumerate(b):
        f = 0
        temp = [0] * i
        for _, y in enumerate(a):
            f, s = divmod(x * y + f, 10)
            temp.append(s)
        if f > 0:
            temp.append(f)
        res.append(temp[:])
    return s_add(*res)


def add(a: str, b: str):
    x = parse(a)
    y = parse(b)
    return dump(s_add(x, y))


def multi(a: str, b: str):
    x, y = parse(a), parse(b)
    return dump(s_multi(x, y))


def e020():
    res = "1"
    xs = [str(x + 1) for x in range(100)]
    for x in xs:
        res = multi(res, x)
    print(sum(map(int, res)))


if __name__ == "__main__":
    e020()