Algorithm(알고리즘)/백준

26_백준 11050번 파이썬 이항계수

고로케 2021. 6. 22.
반응형

이항계수가 뭔지 찾아봤다
수학적 지식이 있어야 풀 수 있는 문제

 이항계수( binomial coefficient ) 는 경우의 수를 계산할때 사용하는 것
 n개의 서로다른 것 들 중에서 k 개를 선택하는 것의 조합(combination)의 경우의 수를
 구하는 것이다.
 
(n)
(k) 는 nCk 조합으로 나타낼 수 있다.

nCk-> factorial(n)//(factorial(k)*factorial(n-k))

팩토리얼(Factorial)은 반복문과 재귀 두가지 방법으로 표현 할 수 있다.

 

* 재귀문 풀이

from sys import stdin

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)

n, k = map(int, stdin.readline().split())
print(factorial(n) // (factorial(k) * factorial(n - k)))

 

 

 

* 반복문 풀이

from sys import stdin
def factorial(n):
    if n == 0:
        return 1
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result


n, k = map(int, stdin.readline().split())
print(factorial(n) // (factorial(k) * factorial(n - k)))

반응형

댓글