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백만을 넘는 경우는 모두 몇 번입니까? (단, 중복된 값은 각각 계산합니다)
간만에 풀었다.
간단한데 문제를 자꾸 이해 못해서 몇 번 고침.
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 |