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

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

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

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

nCr =

n! r!(n−r)!

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

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

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

간만에 풀었다.

간단한데 문제를 자꾸 이해 못해서 몇 번 고침.

from math import factorial

def get_combinatorics(n, r):
    return int(factorial(n) / (factorial(r)*factorial(n-r)))

def is_over_million():
    cnt = 0
    for n in range(23, 101):
        for r in range(0, n+1):
            result = get_combinatorics(n, r)
            if result > 1000000:
                cnt += 1
    return cnt

저작자표시비영리

'개발 > 알고리즘 문제' 카테고리의 다른 글

1 ≤ n ≤ 100 일때 nCr의 값이 1백만을 넘는 경우는 모두 몇 번?  (0)	2018.01.16
[Codility] CountDiv  (0)	2017.11.14
[Codility] MaxCounters  (0)	2017.11.13
[Codility] MissingInteger  (0)	2017.11.12
[Codility] FrogRiverOne  (0)	2017.11.10
[Codility] PermCheck  (0)	2017.11.09