nCr = n-1Cr + n-1Cr-1 을 이용하여 nCr을 구하는 재귀함수가 있습니다.
이렇게 생긴 앤데요 :
| | long long int choose2 (int n, int r) { if(memo[n][r]>0) return memo[n][r]; if(r==0 || n==r) return memo[n][r]=1; return memo[n][r] = choose2(n-1, r-1)+choose2(n-1,r); } | cs |
(보기만 해도 아시겠지만 memo는 값을 저장하기 위해 있는 배열입니다)
이때, nCr을 구하기 위해 저 choose2라는 함수를 호출하는 횟수를 n과 r에 대한 식으로 나타내야 합니다.
..도저히 감이 안 잡혀서 일단 노가다를 했는데요.
파스칼의 삼각형에 넣어보니 등차수열이 있는 걸 발견할 수 있었고, 호출횟수 역시 구할 수 있었습니다.
하지만 왜 저렇게 되는지 제 머리로는 이해가 되지 않습니다..ㅜㅜ 책에도 풀이가 없고.. 어떻게 검색해봐야 할지도 모르겠고.. 왜 저게 등차수열이 될까요??
