이항 계수 1

https://www.acmicpc.net/problem/11050

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	42981	27783	23982	64.497%

예제 입력 1

5 2

예제 출력 1

10

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 수학
• 구현
• 조합론

---

이항정리의 개념과 팩토리얼을 구현하는 간단한 문제

https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EC%A0%95%EB%A6%AC <- 이항정리

이항정리를 모른다면 아래 동영상을 시청하여 개념을 잡는 것을 추천

---

통과된 코드

정의를 그대로 코드로 구현하였다.

#include <iostream>

using namespace std;

int N, K;

// 팩토리얼을 계산하는 함수
int factorial(int number)
{	
	int result = 1;
	for (int i = 1; i <= number; i++) {
		result = result * i;
	}

	return result;
}

int main()
{
	cin >> N >> K;
	cout << factorial(N) / (factorial(K) * factorial(N - K));
	return 0;
} 

이항정리의 개념을 알고 있다면 팩토리얼을 구현하고 계산하면 정답

---

DP문제를 위해서 알아야할 개념

#include <iostream>

using namespace std;

// arr[i][j] 
// i 총 숫자의 개수
// j 선택 개수
// i 개중 j개를 뽑았을때 조합 경우 수
int arr[11][11];

// DP 배열을 초기화 해주는 함수
void DP_Initialiaztion()
{
	for (int i = 1; i < 11; i++) {
		arr[i][1] = i; // i개 중 1개를 뽑는 경우의 수는 i개
		arr[i][0] = 1; // i개 중 1개도 선택하지 않는 경우의 수는 1개
		arr[i][i] = 1; // i개 중 i개를 선택하는 경우의 수는 1개
	}

}

int main()
{
	DP_Initialiaztion();

	return 0;
}

조합의 점화식

nCr = (n-1)Cr + (n-1)C(r-1) 

D[i][j] = D[i-1][j] + D[i-1][j-1]

위의 로직을 이용한 통과 코드

#include <iostream>

using namespace std;

// arr[i][j] 
// i 총 숫자의 개수
// j 선택 개수
// i 개중 j개를 뽑았을때 조합 경우 수
int arr[11][11];

// DP 배열을 초기화 해주는 함수
void DP_Initialiaztion()
{
	for (int i = 1; i < 11; i++) {
		arr[i][1] = i; // i개 중 1개를 뽑는 경우의 수는 i개
		arr[i][0] = 1; // i개 중 1개도 선택하지 않는 경우의 수는 1개
		arr[i][i] = 1; // i개 중 i개를 선택하는 경우의 수는 1개
	}

}

int main()
{
	int N, K;
	cin >> N >> K;
	DP_Initialiaztion();

	// 점화식으로 배열 완성하기
	// i가 2부터 시작하는 이유
	// i가 1일 경우는 초기화가 되어있음
	for (int i = 2; i <= N; i++) { 
		for (int j = 1; j < i ; j++) { // j 0 은 초기화가 되어있음
			arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];
		}
	}

	cout << arr[N][K]; // 결과 출력하기

	return 0;
}