[BOJ 13239 // C++] Combinations

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 13239번 문제인 Combinations이다.
문제는 아래 링크를 확인하자.

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

13239번: Combinations

n과 k가 주어질 때, n개 중 k개를 순서없이 고르는 경우의 수인 조합의 값(을 1,000,000,007로 나눈 나머지)을 계산하는 문제이다.

 

파스칼의 삼각형을 미리 계산해두고 n과 k를 입력받을 때마다 값을 바로바로 리턴하는 것으로 문제를 해결하자. (나머지 연산을 해야 함을 잊지 말자.)

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int T;
int comb[1001][1001];

void combinit() {
	for (int n = 1; n < 1001; n++) {
		comb[n][0] = comb[n][n] = 1;
		for (int i = 1; i < n; i++) {
			comb[n][i] = comb[n - 1][i - 1] + comb[n - 1][i];
			if (comb[n][i] > 1000000006) comb[n][i] -= 1000000007;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	combinit();

	cin >> T;
	while (T--) {
		int n, k; cin >> n >> k;
		cout << comb[n][k] << '\n';
	}
}