[BOJ 2407] 조합

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

2407번: 조합

---

조합은 nCm = n-1Cm + n-1Cm-1 와 같은 특성을 가지고 있다. 이를 이용하여 nCm을 구할 수 있다.

 

하지만 n, m의 범위가 5 ~ 100이므로 unsigned long long로 배열을 구성해도 오버플로우가 발생한다. 

 

이를 막기 위해서는 string을 이용하여 계산을 하거나, 자리수를 나누어 계산할 수 있다.

 

아래의 코드는 대략 앞 17자리, 뒤 17자리의 수를 저장할 구조체를 만들어 풀었다. 

---

#include <stdio.h>
#include <math.h>

const unsigned long long max = 1e17;

typedef struct S
{
	unsigned long long high;
	unsigned long long low;
}S;

S s[101][101];

S Add(S s1, S s2)
{
	S _s = { 0,0 };
	_s.high = s1.high + s2.high;
	_s.low = s1.low + s2.low;
	if (_s.low >= max)
	{
		_s.high++;
		_s.low -= max;
	}
	return _s;
}

S C(int n, int m)
{
	if (s[n][m].low != 0 || s[n][m].high != 0) return s[n][m];
	else if (n == m || m == 0)
	{
		s[n][m].low = 1;
		return s[n][m];
	}
	else
		return s[n][m] = Add(C(n - 1, m), C(n - 1, m - 1));
}

int main() {
	int n, m;

	scanf("%d %d", &n,&m);
	if (n - m < m) m = n - m;
	C(n, m);

	if (s[n][m].high != 0) printf("%llu", s[n][m].high);
	printf("%llu", s[n][m].low);
}