백준 11050번 이항계수1 - Python

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 (N K)를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 �\(K\)가 주어진다. (1 ≤ N ≤ 10, 0 ≤ K ≤ N)

출력

(N K)를 출력한다.

예제 입력 1 

5 2

예제 출력 1 

10

위 문제를 푸는 접근법은 여러개가 있지만 난이도 브론즈1의 수준이라면 팩토리얼을 활용하여 값을 구하는 방법이 적절하다고 생각됩니다 DP를 활용한 해결법, 전체를 순회하면서 수학 본질로 접근해서 N번을 돌아서 K번 일치한 횟수라는 접근이 있습니다.  

풀이

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

N,K = map(int,input().split())
print(int(factorial(N)/(factorial(N-K) * factorial(K))))

 

위 문제를 import math를 하여 factorial 모듈을 활용해서 풀어도 됩니다

직접 구현한 factorial를 사용하는 부분에 math.factorial() 함수로 바꿔써도 직접 재귀함수를 만든 factorial과 동일하게 정상적인 값을 반환합니다

 

추가적으로 아래에 정리가 잘 된 블로그에서 이항계수 구하는 것을 수학 본질로서 접근하여 문제를 해결할 뿐 아니라 다양한 활용도 가능함을 설명하므로 같이 학습하면 좋습니다

참고링크 : https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients

[조합론] 이항계수 알고리즘 3가지