[알고리즘] 파스칼 삼각형을 활용한 조합 계산

1. 파스칼 삼각형

출처 : https://blog.naver.com/vollollov/220947452823?photoView=3

 

출처 : https://blog.naver.com/vollollov/220947452823?photoView=4

 

2. 소스 코드(C++)

int Combination[53][53];

// 조합 계산 함수
int cal_combination(int n, int r) {
	
	if (Combination[n][r]) return Combination[n][r];	// 이전에 계산해놓은 값이 있으면, 바로 반환
	else if (n == r || r == 0) Combination[n][r] = 1;	// n=r 이거나, r = 0일 때, 1 반환
	else {
		Combination[n][r] = cal_combination(n - 1, r) + cal_combination(n - 1, r - 1) % MOD;	// nCr = n-1Cr + n-1Cr -1
	}

	return Combination[n][r];
}