[Project Euler] 53. 1 ≤ n ≤ 100 일때 nCr의 값이 1백만을 넘는 경우는 모두 몇 번?

53. 1 ≤ n ≤ 100 일때 nCr의 값이 1백만을 넘는 경우는 모두 몇 번?

1,2,3,4,5 다섯 숫자 중에서 세 개를 고르는 것에는 다음과 같은 10가지 경우가 있습니다.

123, 124, 125, 134, 135, 145, 234, 235, 245, 345

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

nCr =

n! r!(n−r)!

, 단 r ≤ n 이고, n! = n×(n−1)×...×3×2×1 이며 0! = 1.

이 값은 n = 23 에 이르러서야 23C10 = 1144066 으로 처음 1백만을 넘게 됩니다.

1 ≤ n ≤ 100 일때 nCr의 값이 1백만을 넘는 경우는 모두 몇 번입니까? (단, 중복된 값은 각각 계산합니다)

Click

nCr = nCn-r 이고,
r < n/2 일 때, r1>r2 이면 nCr1 > nCr2 이다.
즉 100만이 넘는 nCr2를 구하면 n/2 보다 작고 r2보다 큰 r1 에 대하여 nCr1 은 100만을 넘으며, nCn-r1 도 역시 100만을 넘는다.

nCr = n!/(r!(n-r)!) 을 풀면.
nCr = n/1 * (n-1)/2 * (n-2)/3 * ....... * (n-r+1)/r 이 된다.

i를 1부터 100까지 증가해 가며,
각 i 마다 i/2 까지 (i-(j-1))/j 를 곱해가며 해당 값이 100만을 넘으면
i/2 - j 의 2배의 값을 더해준다.

<script language="Javascript" type="text/javascript">
function p053(){
    var r = 0;
    for(var i=1; i<=100; i++){
        var temp=1
        for(var j=1; j <= i/2 && temp < 1000000; j++)
            temp *= (i-(j-1))/j;
        if(temp >= 1000000)
            r += ((i+1)/2-(j-1))*2;
    }
    
    alert(r);
}
</script>

time : 0.001(s)

---

오랜만에 문제를 푸네요.
취직을 하여 바빠지니 아무래도 하루 한문제는 이제 힘들 듯 하고..
1주일에 한문제로 하향 조정해야 할 듯합니다.