76.이항계수(메모이제이션)

강지훈·2021년 12월 14일
0

이항계수는 N개의 원소를 가지는 집합에서 R개의 원소를 뽑아 부분집합을 만드는 경우의 수
를 의미한다. 공식은 nCr 로 표현된다.
N과 R이 주어지면 이항계수를 구하는 프로그램을 작성하세요.
▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=20)과 R(0<=R<=20)이 주어진다. 단 (N>=R)
▣ 출력설명
첫 번째 줄에 이항계수 값을 출력한다.
▣ 입력예제 1
5 3
▣ 출력예제 1
10

#include

using namespace std;
int dy[21][21];

int sum=1;
int recur(int n,int r){
if(dy[n][r]>0) return dy[n][r]; //메모이제이션
if(n==r || r==0){
return 1;
}
else {
return dy=[n][r]=recur(n-1,r-1)+recur(n-1,r);

}

}
int main() {
int n , r;
cin>>n>>r ;
cout<<recur(n,r);

return 0;

}

//5c3
5명중에 3명뽑는 것
4c2 + 4c3 네명중에 2명뽑아라 (난 무조건참여) + 네명중에 3명다뽑아라 (난 불참여)

profile
never stop

0개의 댓글