Home » 오일러 프로젝트 53

오일러 프로젝트 53

이번문제는 조합(경우의 수)과 이항정리에 대한 내용이다.

1, 2, 3, 4, 5 다섯 숫자 중에서 세 개를 고르는 것에는 다음과 같은 10가지 경우가 있습니다.
123, 124, 125, 134, 135, 145, 234, 235, 345

조합론이라는 분야에서는 이것을  \binom{5}{3} = 10 이라고 표시하며, 일반적인 식은 아래와 같습니다.

\binom{n}{r} = \frac{ n! }{r!(n-r)!}

이 값은 n = 23에 이르러야  _{23}C_{10} = 1144066 으로 처음 1백만을 넘게 됩니다. 그렇다면 1 <= n <= 100 일 때 nCr의 값이 1백만을 넘는 경우는 모두 몇 번입니까? (단, 중복된 값은 각각 계산합니다.)

접근

조합의 가지수를 계산하는 공식이 문제에 주어져 있으므로, 팩토리얼 계산 함수를 만들어서 계산하면 된다. 엄청 큰 값이 나올 수 있겠지만 파이썬의 경우 큰 수 연산을 지원하므로 어렵지 않게 풀어낼 수 있다. nCr 에서 r은 n 이하의 수만 나올 수 있다는 점에 유의해서 백만보다 큰 경우를 세면 된다.

from functools import reduce
def factorial(n):
  if n < 2:
    return 1
  return reduce(lambda x, y: x*y, range(2, n+1))
def nCr(n, r):
  return factorial(n) // factorial(n - r) // factorial(r)
def p053():
  c = 0
  for n in range(1, 101):
    for r in range(1, n):
      if nCr(n, r) >= 100_0000:
        c += 1
  print(c)

파이썬의 큰 수 계산 능력은 깡패수준이기 때문에 이 계산은 순식간에 처리되고 답이 나온다. 큰 수 연산을 사용하지 않는다면 어떻게 계산할 수 있을까?

참고로 100이하의 nCr 에서 나올 수 있는 최대 값은 100,891,344,545,564,193,334,812,497,256이다.

이항정리

nCr은 n개 중에서 r 개를 고르는 가짓수를 계산하는 방법이다. n 개 중에서 r개를 고르는 상황을 좀 자세히 들여다보다. n 개 중에서 한 개 요소를 고를 때 우리가 선택할 수 있는 것은 그 한 개를 선택하는 경우와 선택하지 않는 경우가 있다. 만약 한 개를 선택했다면, 남은 n-1 개 중에서 r-1개를 선택하면 되고, 선택하지 않았다면 남은 n-1 개 중에서 r 개를 선택하면 된다.

따라서 n개중에서 r개를 선택하는 경우의 수는 n-1개에서 r개를 선택하는 경우 + n-1개에서 r-1개를 선택하는 경우로 계산할 수 있다. 이를 식으로 쓰면  _nC_r = _{n-1}C_{r-1} + _{n-1}C_r 이고 이것이 이항 정리이다.

이항 정리의 원리를 사용하면 이 문제는 동적 계획법으로 풀 수 있는 상황이 된다.

  1. 100 x 100 크기의 그리드가 있다고 하자. 기본적으로 모두 0으로 초기화된다.
  2. 가로는 n=1,2,3,4,…, 100, 세로는 r=1,2,3,4,..,100 으로 그리드의 각 값은 해당 행/열 인덱스로부터 nCr를 계산한다.
  3. 첫 열의 각 값은 nC1 이기 때문에 n 값과 같다.
  4. 가로, 세로가 모두 같은 위치에서는 nCn이기 때문에 모든 대각선에 위치한 셀의 값은 1이다.

이렇게 준비된 그리드의 두 번째 행의 두번째 열부터 위쪽 셀의 값과 왼쪽위셀의 값을 더해서 현재 셀의 값을 만든다. 이때, 백만 보다 더 큰 값을 정확히 저장할 필요가 없으므로 백만보다 크다면 1,000,001을 저장하면 된다. 이렇게 계산하고 백만 보다 큰 값을 세면 끝이다.

def s053():
    "이항 정리를 활용한 동적 계획법 풀이"
    s = [0] * 10000
    s[0::100] = [i + 1 for i in range(100)]
    s[0::101] = [1] * 100
    for n in range(1, 100):
        for r in range(1, n):
            s[n*100+r] = min(s[n*100+r-100] + s[n*100+r-101], 100_0001)
    print(sum(1 for x in s if x > 100_0000))
    

아래는 동일한 알고리듬의 줄리아 구현이다. 줄리아의 경우, 배열 인덱스가 1부터 시작하며, 범위의 끝값을 포함하기 때문에 2차원 배열을 사용하는 것이 좀 더 자연스럽다.

using LinearAlgebra # for diagind
let s = zeros(Int, (100, 100))
  s[:, 1] = 1:100
  s[diagind(s)] = ones(Int, 100)
  for n=2:100
    for r=2:n-1
      s[n, r] = min(100_0001, s[n-1, r] + s[n-1, r-1])
    end
  end
  count(==(100_0001), s) |> println
end

댓글 남기기