백준 11050번 이항 계수 1 [C/C++]

11050번: 이항 계수 1

이항 계수 개념은 조합의 설명을 보면 알 수 있습니다. 조합은 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것인데, 그 경우의 수가 이항계수입니다. 이 이항계수를 나타내는 방법은

 

$$ _n \mathrm{ C }_k$$

 

또는

로 나타낼 수 있습니다.

 

요약하자면 이항 계수는 조합의 가짓수를 뜻하고, 이항의 의미는 뽑거나, 안 뽑거나 두 가지의 경우만 있기에 이항이라는 단어가 붙었습니다.

 

이항계수 구하는법

1. n! / k!(n-k)! 를 그대로 구현하는 방법.
2. 점화식을 사용하기.

저는 구현할 때 점화식을 사용해 재귀로 구현했고, 이항계수 점화식은 다음과 같습니다.

즉, nCk의 값을 구할 때는 위 식처럼 다른 조합의 식 2개를 활용하여 구할 수 있습니다. 

 

 이해를 돕도록 점화식을 조금 더 직관적으로 확인할 수 있는 방법으로 파스칼의 삼각형을 들고 왔습니다. 위 처럼 3과 3이 합해져 6이라는 결과가 나온 것을 확인할 수 있습니다. 그리고 위 점화식을 사용하여 재귀를 만들때 재귀함수의 base case는 위 파스칼의 삼각형에서 확인할 수 있는데, 조합의 n과 k가 같을 때 1인경우와, k가 0일때 1인 경우를 이용하여 설정하였습니다.

 

코드

#include <iostream>

//static int binomial로 선언가능.
int binomial(int n, int k)
{
	if (n == k || k == 0) {
		return 1;
	}

	//재귀를 보는 관점 : n-1Ck-1까지의 합과 n-1Ck까지의 합을 더한 것.
	return binomial(n-1, k-1) + binomial(n-1, k); 

}

int main()
{
	int n, k;
	std::cin >> n >> k;

	std::cout << binomial(n, k);

	return 0;
}

 

 

 

 

 

 

 

 

 

---

 

본문과는 다른 내용이지만 혹시 조합 수식을 표시 해놓는 것이 궁금하신 분이 계실까봐 남겨놓습니다. (미래의 나를 위해서도..)

위키백과:TeX 문법 - 위키백과, 우리 모두의 백과사전

위 위키에 있는 대로

$$ _{n}\mathrm{C}_{k} $$를 치면 수식적용이 안되는데,

Permutation And Combination method in MathJax using Asscii Code

스택 오버플로우에 나와있는 수식을 $$ $$로 감싸서 작성하니 되었습니다. 

 

https://artiper.tistory.com/manage/newpost/70?type=post&returnURL=https%3A%2F%2Fartiper.tistory.com%2F70

티스토리에서 수식입력을 가능하게 하는 방법 링크도 남겨놓습니다.

 

이거는 latex로 입력하는 방법은 못찾겠어서 그냥 이미지로 짤라붙임..