문제:

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

입력:

첫째 줄에 N과 K가 주어진다. (1<= N <=10, 0<=K <=N)

출력:

(N K)를 출력한다.

풀이 방법:

이 문제는 이항 계수를 재귀함수로 구현을 해서 풀어야 하는 문제 였다. 파스칼의 법칙에 의해서 이항계수는 다음과 같은 공식을 가진다.

  C(n ,k) =C(n-1,k-1)+C(n-1,k)

따라서 이를 general case, 즉 크기가 감소되는 케이스로 분류를 한다. 또한 이항계수는 C(n,0) ,C(n,n)일 때 항상 1이라는 값을 가진다. 따라서 이 경우는 base case로 재귀가 끝나는 경우로 분류를 한다.


1
2
3
4
5
6
7
8
9
10
11
a,b=map(int,input().split())
 
def binomial(n,k):
    if n==k:
        return 1
    elif k==0:
        return 1
    else:
        return binomial(n-1,k-1)+binomial(n-1,k)
    
print(binomial(a,b))
cs


'Algorithm > Python' 카테고리의 다른 글

[BOJ]1676. 팩토리얼 0의 개수  (0) 2019.05.10
[BOJ]11051. 이항 계수 2  (0) 2019.05.09
[BOJ]11050. 이항 계수 1  (0) 2019.05.08
[BOJ]11866. 조세퍼스 문제0  (0) 2019.05.07
[Programmers]Lv 3.디스크 컨트롤러  (2) 2019.05.06
[BOJ]8979. 올림픽  (0) 2019.05.05

+ Recent posts