Project Euler #53 - Combinatoric selections

프로젝트 오일러 53번 - 조합의 개수
n이 100 이하일 때, nCr이 100만을 넘어가는 경우는 몇 번인가?

가장 나이브한 방법
n = 1, 2, 3, ..., 100에 대해서
모든 r = 1, 2, ..., n 에 대해서
nCr을 계산하고, 100만을 넘는 경우를 센다.

몇 가지 생각할 것들
1. 문제에서 n = 23에서 처음으로 100만을 넘는다고 했다. n = 23, 24, 25... 100을 체크하면 된다.
2. nCr = nC(n-r)과 같다. 그리고, r = 2/n일 때 최대가 된다. r = 1, 2,...를 체크하다가 100만을 넘어가면 그만 체크해도 된다.
3. nCr = n! / (n-r)!(r)! = n! / (n-r+1)!(r-1)!  /r * (n-r+1) = nC(r-1) / r * (n-r+1), 즉, 매번 nCr을 계산하는 대신, nC(r-1)의 결과를 업데이트하는 방식으로 쉽게 계산할 수 있다.
3.1. nCr은 항상 자연수이므로 '곱셈-나눗셈'의 순서만 지킨다면 오차를 걱정할 필요는 없다.

def fromn(n):
    nCr = n
    for i in range(1,int(n/2)):
        nCr *= (n-i)
        nCr /= (i+1)
        if nCr > 1000000:
            return n-2*i-1
    return 0

rs = 0

for i in range(23,101):
    rs += fromn(i)

print rs

계산 시간은 0.3ms

for i in range(1,int(n/2)+1)) 로 쓰는 것이 좀 더 안전해 보인다. 그런데, 23C10 에서 처음으로 100만을 넘는다는 걸 아는 상태에서는 위험할 것도 없다.