키큰개발자

문제사이트 : http://codeup.kr/problem.php?id=1925

해결 방법 :

nCr을 구하기 위해서 생각해보면, 

n개 중 r개를 뽑는 것은  

n개 중 먼저 하나를 보는데 이게 뽑혀져있는 상황에서 r-1개(하나가 먼저뽑혓다)를 뽑는 경우 + n개 중 하나를 먼저 보는데 이게 안뽑혀있는 상황에서 r개를 뽑는 경우의 수랑 같다는 것을 아는 것이 이 문제를 푸는 핵심인것 같다.

이제 이를 이용해서 점화식을 세운다면, 

 가 된다.

이식을 바탕으로 재귀함수를 디자인하면 된다.

기저조건은 r 부분이 0이 되거나 혹은 n과 r이 같을 때 이 두가지로 나눌수있다.

기저조건이 아닐때는 점화식대로 재귀함수를 호출해주면 된다.