오일러 프로젝트 53

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

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

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

 

 

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

 

 

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

접근

문제에 나와있는대로 팩토리얼을 이용해서 조합의 가지수를 계산해서 해당 값이 1백만을 넘는 경우를 카운트하면 된다. 왠지 아주 큰 값이 튀어나올 소지가 있지만, 파이썬이라면 일단 문제가 안될테니 무식하게 돌려보면 아래와 같은 코드로 풀어낼 수 있다.

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 에서 나올 수 있는 최대 값은 100891344545564193334812497256이나 되기 때문에 포기하는 것이 편하다.

약분을 우선수행하기

nCr의 계산은 분수식인데, 이 때 이 결과는 항상 정수값이 되므로 분자는 모두 약분됨을 알 수 있다. 따라서 분자와 분모에 각각 곱해지는 정수 목록을 두고 이들을 약분한 다음, 분모에 남은 값들을 계산한다. 계산을 수행하는 과정에서 백만이 넘는 부분을 체크할 수 있다. 이를 Swift 코드로 작성하면 아래와 같이 작성할 수 있다.

// 최대공약수 계산 함수
func gcd(_ a:Int, _ b:Int) -> Int {
  if a < b { return gcd(b, a)
  if b == 0 { return a }
  return gcd(b, a % b)
}

// 분모, 분자에 쓰이는 수들을 받아 약분 후 계산하는 함수
func abbr(_ a: [Int], _ b: [Int]) -> Int? { // 100만을 넘어서면 nil 리턴 
  var a = a
  for var y in b {
    for (i, x) in a.enumerated() {
      if y == 1 { break }
      if case let g = gcd(x, y), g > 1 {
        y = y / g
        a[i] = x / g
      }
  }
  var result = 1
  for x in a {
    result *= x
    if result > 100_0000 { return nil } 
  }
  return result
}

func p053() {
  c = 0
  for n in 1...100 {
    for r in 1..<n {
        if abbr(Array(1...n), Array(1...r) + Array(1...n-r)) == nil {
           c += 1
        }
    }
  }
}

p053()  

이항정리

위의 방식으로 풀었을 때 답은 나오지만, 좀 껄적지근한 느낌을 지울 수가 없다. (그리고 루프를 꽤 많이 돌아야 하기 때문에 통상 2초 이상의 시간이 걸렸다.) 이 문제를 풀기 위해서는 “이항정리”에 대한 내용을 조금 알 필요가 있다. n 개 중에서 r 개를 꺼내는 가지수를 구하는 조합에서 어떤 임의의 요소 1개를 고정했다고 가정하자. 그러면 n 개 중에서 r 개를 꺼내는 경우는 그 고정된 1개를 포함하거나 포함하지 않거나 중 하나이다. 따라서 다음 두 경우에 대한 경우의 수의 합으로 nCr 을 구할 수 있다.

  1. (n – 1) 개 중에서 (r – 1) 개를 고르는 경우의 수
  2. (n – 1) 개 중에서 r 개를 고르는 경우의 수

이를 식으로 쓰면 _nC_r = _{n-1}C_{r-1} + _{n-1}C_r 이 된다. 이건 마치 어떤 점화식처럼 생기지 않았나? 2차원 배열을 이용한 동적 계획법으로 이 모든 케이스를 구할 수 있다.

  1. 2차원 배열을 준비한다. 총 100행 X 100열의 크기이다.
  2. 이 때 행은 n, 열은 r이라고 한다.
  3. 첫번째 행은 _nC_1 이므로  n의 값과 동일하다.
  4. r은 1…n 사이의 범위이기 때문에 (x, x)의 위치는 모두 1의 값이어야 한다.
  5. 참고로 배열의 인덱스는 0부터 시작하기 때문에 여분(?)의 행과 열을 추가한다.

이렇게 준비된 그리드의 두 번째 행의 두번째 열부터 왼쪽셀의 값과 왼쪽위셀의 값을 더해서 현재 셀의 값을 만든다. 여기서 요건은 100만보다 큰지 아닌지를 알면 되기 때문에 이 값이 100만을 넘어서면 항상 100,0001 이 저장되도록 한다. 이후 2차원 배열을 하나로 연결하고 100만이 넘는 항의 개수를 세면 끝.

func p053() {
  var grid = (0...100).map{ Array(repeating: 0, count: 101) }
  /// nC1 = n 이므로 해당 칸을 업데이트한다.
  grid[1] = Array(0...100)
  /// nCn = 1 이므로 해당 칸을 업데이트한다.
  (1...100).forEach{ grid[$0][$0] = 1 }
  for row in 2...100 {
    for col in row...100 {
      let x = grid[row-1][col-1] + grid[row][col-1]
      grid[row][col] = x > 100_0000 ? 100_0001 : x
    }
  }
  print(grid.flatMap{$0}.filter{$0 > 100_0000}.count)
}
p053()