Backjoon 11051 / 이항계수 / DP(다이나믹 프로그래밍)

* Part 01 개념 분석

이항 계수는  == 나  의 두 가지 표현 방법 있다.

 의 정의는 아래 주소를 참고해주면 좋겠다.

위키백과 - 이항계수 (https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98)

* 파스칼 삼각형

위는 파스칼의 삼각형을 뜻한다.
이항 계수의 값을 삼각형 모양으로 나열한 표를 파스칼 삼각형이라고 한다.

nCk = n-1Ck-1 + n-1Ck(n!=k, k!=0) 의 식이 적용되는 삼각형이다.

위 식을 적용시켜서 11051번의 문제를 풀었다.

* Part 02 문제분석 

위의 개념을 그대로 적용하는 문제이지만, 10007을 나눈 나머지를 구하는 점만 다르다는 것을 유의하자.

* part 03 문제 풀이

#include<stdio.h>
int arr[1001][1001]; //전역변수로 배열 선언
int main(void)
{				
	int n,k; //nCk에서 n과 k
	scanf("%d %d", &n, &k);
	 
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0 ;j <= k;j++)
		{	//파스칼 삼각형 & 이항계수 식 적용 location
			if (j == 0 || i == j) arr[i][j] = 1;						//k가 0이거나 같은 경우에는 1이기에 
			else arr[i][j] = (arr[i - 1][j] + arr[i - 1][j - 1])%10007; //nCk = n-1Ck-1 + n-1Ck
			//나중에 한꺼번에 나누기 보다
			//나누면서 더해준다. memory overhead를 막기 위해
		}
	}
	printf("%d\n", arr[n][k]); //print 부분
	return 0;
}