오일러 프로젝트 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끼리의 순서는 구분이 없다. 따라서 전체 경로의 길이는 다음 식으로 구해진다.
따라서 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 이상)인 경우에 서로를 나눠준다.
- 이렇게하여 모든 분자 인수 리스트의 값이 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)
