[백준] 11051번. 이항 계수2

[백준] 11051번. 이항 계수2

1. 문제

자연수 N과 정수 K가 주어졌을 때 이항 계수를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

2. 입력

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

3. 출력

이항 계수를 10,007로 나눈 나머지를 출력한다.

4. 풀이

이항 계수 정의

• 파스칼의 삼각형을 이용하여 풀었다.

파스칼의 삼각형

• 파스칼의 삼각형의 값을 배열에 저장하고 배열의 값을 출력했다.

5. 처음 코드와 달라진 점

• 멍청하게 N을 계속 쳐다봐놓고 배열 크기를 1000까지로 했다.
• 좌우가 똑같으니까 반만하고 나머지 반은 안 해야지 했는데 사소한 오류가 자꾸 나길래 그냥 전부 다 구했다.

6. 코드

#include <iostream>
using namespace std;

long long d[1001][1000] = { 0, };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, k;
	cin >> n>>k;

	d[0][0] = 1;
	d[1][0] = 1;
	d[1][1] = 1;
	for (int i = 2; i <= n; i++){
		d[i][0] = 1;
		for (int j = 1; j <= i; j++){
			d[i][j] = (d[i - 1][j - 1] + d[i - 1][j])%10007;
		}
	}

	cout << d[n][k];
}