#11051 이항 계수 2

# 문제

# 입력 및 출력

# 풀이

처음에 풀었던 방법이 하나하나 계산해주는 방법이었다

// 틀린 풀이
#include <iostream>
using namespace std;
int com[1001] = { 1, };

int main() {
	int n, k;
	cin >> n >> k;
	int t = n, b = 1;
	for (int i = 1; i <= k; i++) {
		com[i] = (com[i - 1] * t / b) % 10007;
		t--, b++;
	}
	cout << com[k] << "\n";
}

이렇게 하니까 도중에 소수점이 나오는 경우가 생겼다

https://youseokhwan.me/blog/remainder-distribution-property/

나머지 연산 분배법칙

위 블로그를 읽어보면 나눗셈엔 나머지 연산의 분배법칙이 적용되지 않기 때문에

10007로 나눠 나온 나머지 값을 배열에 저장해두고 계산할 때 계속 사용하면 오류가 생기는 것이다

 

그래서 다른 방법을 찾아보았다

https://wootool.tistory.com/53

[조합] nCr 쉽게 구하기. (수정 20190604)

조합을 구하는 다른 방법이다

 

이렇게 계산하면 덧셈밖에 없기 때문에 나머지 연산도 계속해서 사용이 가능해서

int 범위를 초과하지 않으면서 정확한 결과 값을 구할 수 있다

 

#include <iostream>
using namespace std;
int com[1001][1001];
// nCr = n-1Cr + n-1Cr-1
int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		com[i][0] = 1;
		com[i][i] = 1;
		for (int j = 1; j < i; j++) {
			com[i][j] = (com[i - 1][j] + com[i - 1][j - 1]) % 10007;
		}
	}
	cout << com[n][k];
}

 

 

이젠 슬슬 실버 문제를 졸업하고 골드 문제로 넘어가야 할 것 같다

트리랑 그래프 탐색 부분은 실버 문제로 좀 더 연습하고 dp, 그리디, 수학 부분은 골드로 넘어가서 

문제 하나하나를 깊게 파고들 필요가 있다고 본다