[백준] 이항 계수 1 c++

 

이항 계수 1

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

77878

50490

43711

64.652%

문제

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

입력

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

출력

 (NK)\(\binom{N}{K}\)를 출력한다.

---

 

#include <iostream>

using namespace std;

int main()
{
	int N, K;

	//크기는 N의 최대크기+1
	int D[11][11];

	cin >> N >> K;

	//이항 계수의 기본 규칙을 적용
	for (int i = 0; i <= N; i++)
	{
		D[i][1] = i; // 하나를 고르는 경우 항목 수와 동일
		D[i][0] = 1; // 어떤 수에서 0개를 고르는 경우 1
		D[i][i] = 1; // 자기 자신을 고르는 경우 1
	}

	for (int i = 2; i <= N; i++)
	{
		for (int j = 1; j < i; j++)
		{
			//이항 계수의 점화식
			D[i][j] = D[i - 1][j] + D[i - 1][j - 1];
		}
	}

	cout << D[N][K];
}