오일러프로젝트 015

오일러 프로젝트 015

20X20 격자를 통과하는 경로의 수.

http://euler.synap.co.kr/prob_detail.php?id=15

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

![1](http://euler.synap.co.kr/images/p_015.gif)

그러면 20 × 20 격자에는 모두 몇 개의 경로가 있습니까?

풀이

2 X 2 격자의 가로선을 a, 세로선을 b라하면 좌상단에서 우하단까지의 경로는

  • aabb
  • abab
  • abba
  • baab
  • baba
  • bbaa

가 된다. 이 경로의 가지수는 aabb 를 줄 세우는 순열로 구하는데, 4!로 구하는 경우 a끼리, b끼리는 순서가 바뀌어도 동일하므로 2! x 2!을 나눠준다.

같은 원리로 20×20 격자의 경로수는 40! / (20! * 20!)로 계산한다.

from functools import reduce

def factorial(n):
    if n < 2:
        return 1
    return reduce(lambda x, y:x*y, range(1, n+1), 1)

def p15():
    print(factorial(40)//factorial(20)//factorial(20))

%time p15()
# 137846528820
# Wall time: 0 ns

40!의 값은 64비트 정수 범위를 넘어서므로, 이 값을 정수의 크기 제한이 있는 언어에서 계산하기 위해서는 숫자를 분모, 분자에 나열하고 각각의 숫자들을 약분하여 분자에 남는 수들만 곱해준다.

(40 * 38 * ... * 21) / (20 * 19 * 18 * ... * 1)을 계산한다. 이 값은 필연적으로 정수가 되게 되어 있다.

import Foundation

func timeit(@noescape f:()->()) {
    let startTime = NSDate()
    f()
    let elapsed = NSDate().timeIntervalSinceDate(startTime)
    print("time: \(elapsed * 1000) ms")
}



func gcd(a:Int, _ b:Int)->Int {
    let (max, min) = a > b ? (a, b) : (b, a)
    if max % min == 0 {
        return min
    } else {
        return gcd(min, max % min)
    }
}

timeit {
    var a1 = Array(21...40) // 분자들
    var a2 = Array(1...20) // 분모들
    for i in 0..<20 {
        for j in 0..<20 {
            let g = gcd(a1[i], a2[j])
            if g > 1 {
                a1[i] = a1[i] / g
                a2[j] = a2[j] / g
            }
            if a1[i] == 1 {
                break
            }
        }
    }
    let result = a1.reduce(1, combine:*)
    print(result)
}

//137846528820
//time: 0.562012195587158 ms