Project Euler

프로젝트 오일러 053

nCr이 백만을 넘는 경우 세기

3분
#project euler #python

순열 및 조합의 계산식은 기본적으로 팩토리얼과 관련이 있기 때문에 큰 수의 곱셈과 큰 수의 나눗셈이 연관됩니다. 큰 수의 덧셈이나 큰 수의 곱셈은 파이썬에서 기본적으로 제공하는 기능인 동시에, 다항식의 성질을 이용하여 직접 구현도 해보았습니다. 물론, 큰 수의 나눗셈은 좀 더 다른 문제이기는 합니다.

팩토리얼의 분수식은 분모 분자에서 여러개의 숫자가 약분되어, 결국 몇 개의 숫자들의 곱셈으로 귀결됩니다. 따라서 큰 정수 연산 기능을 사용하여 그냥 계산하거나, 분모, 분자를 반복적으로 약분하여 계산과정에서 큰 수가 나오는 가능성을 최소화하는 방법이 있을 수 있습니다.

그냥 풀기

큰 정수의 연산을 지원하는 언어에서는 nCr 계산식을 함수로 구현해서 직접 계산해보면 됩니다.

참고로 nCr은 n개 중에서 r개를 선택하는 조합의 수입니다. n개 중에 r개를 선택한다는 것은, 같은 말로 r개를 뺀 나머지 것들을 제거하는 것과도 같습니다. 즉 (n - r)개를 선택하는 것과 같습니다. 따라서 nCr = nC(n - r)입니다.

r은 n보다 클 수 없고, nCr = nC(n - r)이기에 r의 범위는 n의 절반까지로 제한할 수 있습니다.

from functools import reduce

prod = lambda xs: reduce(lambda x, y: x * y, xs)
factorial = lambda n: 1 if n < 2 else prod(range(1, n + 1))

def nCr(n: int, r: int) -> int:
    return reduce(lambda x, y: x // y, map(factorial, (n, r, n - r)))


def main():
    res = 0
    for n in range(1, 101):
        for r in range(1, n // 2 + 1):
            if nCr(n, r) >= 100_0000:
                res += 1

    print(res)


if __name__ == "__main__":
    main()

그러나 실제로 계산될 수 있는 가장 큰 값은 백만보다 훨씬 더 큰 수이기 때문에, 충분히 빠르게 답을 계산할 수 있지만 좀 더 나은 방법을 생각해볼 필요는 있습니다.

이항정리

nCr이 n개의 아이템에서 r개를 선택한다는 의미에서 몇 가지 시사점이 있습니다.

  1. 앞서 언급한 바와 같이, n개 중에 r개를 선택하는 것은, n개 중에서 r개를 남기고 (n - r)개를 제거하는 것과 같습니다. 제거하기 위해서는 그만큼을 선택해야 하기에 nCr = nC(n-r)입니다.
  2. n개의 원소 중 특정한 1개에 대해서는 그 원소를 선택하거나, 선택하지 않는 두 가지 경우가 있습니다. 만약 그 원소를 선택했다면 남은 n-1개 중에서 r-1개를 선택하는 경우의 수가 나옵니다.
  3. 반대로 그 원소를 선택하지 않았다면 남은 (n-1)개 중에서 r개를 선택하는 경우의 수가 나옵니다.
  4. 따라서 nCr = (n-1)C(r-1) + nC(r-1)과 같습니다.
  5. 이 점화식의 기저 케이스는 nCn = 1, nC1 = n입니다. 이 점화식은 이항정리라고 부릅니다.

점화식을 알게 되었으니, 더 작은 n, r의 nCr로부터 조합의 수를 계산하는 것이 가능하며, 동적 프로그래밍을 적용할 수 있다는 점을 시사합니다.

  1. n행, r열로 이루어진 그리드가 있고, 각 그리드는 0으로 채워집니다.
  2. 행번호와 열번호가 같은 셀은 1로 채웁니다.
  3. 각 행의 첫번째 셀은 행번호로 채웁니다.
  4. 이제 두 번째행부터 0인 셀에 대해서 왼쪽 위 대각선 셀의 값과 바로 위 셀의 값을 더하여 기록합니다.
  5. 열 번호가 행번호 보다 크다면 다음 행으로 넘어갑니다.

이 과정을 반복하면 그리드의 마지막 셀에는 n과 r보다 작은 수들에 대한 모든 nCr이 구해지게 됩니다. 이 그리드에서 백만을 초과하는 경우만 세면 됩니다. 참고로 정확한 수치가 필요한 것이 아니라 1백만 보다 큰지만 보면 되기 때문에, 합이 백만을 초과하는 경우에는 100_0001로 기록합니다. 이렇게하면 32비트 정수의 범위만 사용해서 답을 구할 수 있습니다.

def main(n: int, r: int) -> None:
    grid = [0] * (n * r)
    # n == r이면 nCr = 1
    grid[:: r + 1] = [1] * n
    # nC1 = n
    grid[::r] = [i + 1 for i in range(n)]
    # 이항정리를 적용하여 계산, 계산과정에서 백만을 넘어가면 100_0001로 한정하기
    for row in range(n):
        for col in range(r):
            if col > row:
                break
            if grid[row * r + col] == 0:
                grid[row * r + col] = min(
                    100_0001, grid[(row - 1) * r + col - 1] + grid[(row - 1) * r + col]
                )
    print(sum(1 for x in grid if x > 100_0000))


main(100, 100)

실제로 동적계획법이 직접 계산하는 것보다 훨씬 빠르며, 문제에서 제시한 범위를 1~1,1000으로 확장하더라도 아주 빠른 시간 내에 답을 구할 수 있습니다.