이항 계수 2

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	49473	18353	14434	37.625%

예제 입력 1

5 2

예제 출력 1

10

출처

• 데이터를 추가한 사람: BaaaaaaaaaaarkingDog, kimsu00215, loveyourself, skyoliver
• 문제를 만든 사람: baekjoon

알고리즘 분류

• 수학
• 다이나믹 프로그래밍
• 조합론

---

전에 풀었던 11050번의 응용 문제

조합에 대한 기본 개념을 가지고 점화식으로 접근해야 해결이 가능하다.

백준 11050번 (이항 계수 1, C++, DP) [BAEKJOON]

---

통과된 코드

#include <iostream>

using namespace std;

constexpr int MAX = 1001;
constexpr int MOD = 10007;

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

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

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

	// 배열 초기화
	DP_Initialiaztion();

	for (int i = 2; i <= N; i++) {
		for (int j = 1; j < i; j++) {
			DP[i][j] = (DP[i - 1][j] + DP[i - 1][j - 1]) % MOD;
		}
	}

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

	return 0;
}

팩토리얼 계산과 모듈러 연산 개념으로 접근했지만 실패

점화식을 이용한 접근으로 해결하였다.