[C++] 이항계수(메모이제이션) ⭐

이항 계수(binomial coefficient)는 조합론(Combinatorics)에서 사용되는 수학적 개념으로, 주어진 크기의 집합에서 원하는 개수의 원소를 선택하는 방법의 수를 나타냅니다. 이항 계수는 주로 "n choose k"로 표기되며, "n choose k"는 n개의 원소 중에서 k개의 원소를 선택하는 경우의 수를 의미합니다.

 

이항 계수의 조합적 특성은 다음과 같습니다:

C(n,k) = C(n−1,k−1) + C(n−1,k)
​

📄문제

이항계수는 N개의 원소를 가지는 집합에서 R개의 원소를 뽑아 부분집합을 만드는 경우의 수
를 의미한다. 공식은 nCr 로 표현된다.
N과 R이 주어지면 이항계수를 구하는 프로그램을 작성하세요.

 

⬇️ 입력

첫 번째 줄에 자연수 N(1<=N<=20)과 R(0<=R<=20)이 주어진다. 단 (N>=R)

5 3

 

⬆️ 출력

첫 번째 줄에 이항계수 값을 출력한다.

10

 

📝 풀이

#include <iostream>

/*
	nCr 은 (n-1 C r-1) + (n-1 C r)로 나뉠 수 있다.

	n==r이 되거나, r이 0이 되면, 경우의 수는 1로 리턴할 수 있다.
	예를들어 5C5와 5C0은 1이다.
*/

// 메모이제이션 (계산된 값을 기억해두기)
int dy[21][21];

int DFS(int N, int R)
{
	// 이미 dy에 값이 있다면 바로 리턴하기
	if (dy[N][R] > 0) return dy[N][R];

	else if (N == R || R == 0) return 1;

	// N,R은 N-1,R-1과 N-1,R로 쪼개어 계산
	else return dy[N][R] = DFS(N - 1, R - 1) + DFS(N - 1, R);
}

int main()
{
	int N, R;
	scanf_s("%d %d", &N, &R);

	printf("%d", DFS(N, R));
}

• 재귀를 이용하여 nCr을 두개의 합으로 쪼갭니다. 쪼갠 합을 dy에 저장하고, 추후에 재사용할 수 있도록 합니다.