[Project Euler] 53. Combinatoric selections

1. 개요

    문제는 이곳에서 확인할 수 있다. 100만보다 큰 \(_nC_r\)의 개수를 구하는 것이 문제의 목표이다. 단, \(1<=n<=100\)이며 중복을 허용한다.

2. 구현

    \(_nC_r=_nC_{n-r}\)을 이용한다.

# -*- coding: utf-8 -*-
# Project Euler 53

import sympy

ans = 0

for n in range(23, 101):
    tmp_ans = 0

    for r in range(n//2, -1, -1):
        if sympy.binomial(n, r) <= 1e6:
            break

        tmp_ans += 1

    ans += tmp_ans * 2 - (1 if n % 2 == 0 else 0)

print(ans)

    답은 4075이다.