오일러 프로젝트 15

오일러 프로젝트 15 번 문제는 간단한 경우의 수 문제이다.

아래와 같은 2 × 2 격자의 왼쪽 위 모서리에서 출발하여 오른쪽 아래 모서리까지 도달하는 길은 모두 6가지가 있습니다 (거슬러 가지는 않기로 합니다).

그러면 20 × 20 격자에는 모두 몇 개의 경로가 있습니까?(http://euler.synap.co.kr/prob_detail.php?id=15)

접근

2 X 2 격자의 가로선을 a, 세로선을 b라하면 좌상단에서 우하단까지의 경로는 2개의 a와 2개의 b를 나열하는 경우의 수와 같다. 즉 위의 그림의 각 경로는 a,b문자의 조합으로 보면 각각, aabb, abab, abba, baab, baba, bbaa 로 표현할 수 있다. 4개의 원소를 줄지우는 방법은 총 4!인데, 이 때 두 개의 a와 두 개의 b는 각각 같으므로 a끼리의 순서와 b끼리의 순서는 구분이 없다. 따라서 전체 경로의 길이는 다음 식으로 구해진다.

\frac{w! \times h!}{(w + h)!}

따라서 20X20 격자를 가로지르는 최단 경로의 가짓수는 다음 코드로 구할 수 있다.

## Python 3.6
from functools import reduce

factorial = lambda n: reduce(lambda x, y: x*y, range(1, n+1))
print( factorial(20+20) // factorial(20) // factorial(20))

큰 수이기는 하나 즉시 계산된다.

큰수를 지원하지 않는 언어에서 계산하는 방법

문제에서 분모가 되는 40!은 48자리 정수이며 이 값을 저장하기 위해서는 160비트가 필요하기 때문에 Swift에서는 이를 다룰 수 없다. 대신에 계산전에 분모/분자를 우선 약분하는 식으로 계산을 수행할 수는 있다. 분모/분자가 큰 수를 약분하기 위해서는

  1. 분모와 분자를 구성하는 인수들의 리스트를 각각 인자로 받은 다음,
  2. 각 분자의 인수에 대해서 분모의 인수와 약분가능(최소 공배수가 1 이상)인 경우에 서로를 나눠준다.
  3. 이렇게하여 모든 분자 인수 리스트의 값이 1이 된 후에 분모측에 남은 수들을 곱해준다.

이 함수를 Swift로 작성해보자. 이를 위해서는 먼저 최대공약수를 구하는 함수가 필요하다. (어디선가 앞에서 만들어 본 거 같…)

func gcd(_ a:Int, _ b: Int) -> Int {
    guard b > 0 else { return a }
    return gcd(b, a % b)
}

이번에는 약분하는 함수

func abbr(_ a:[Int], _ b:[Int]) -> (Int, Int) {
  var a = a
  var b = b
  for i in 0..<(b.count) {
    for j in 0..<(a.count) {
      if a[j] == 1 { continue }
      if b[i] == 1 { breal }
      if case let g = gcd(a[j], b[i]), g > 1 {
        a[j] /= g
        b[i] /= g
      }
  }
  return (a.reduce(1, *), b.reduce(1, *))
}

따라서 최종 결과는 다음과 같이 계산된다.

print(abbr(Array(1...40), Array(1...20) + Array(1...20)).0)