[C/C++]Combination 함수에 대해 고민해보기

Algospot의 SNAIL(달팽이) 문제를 푸는 도중 combination 에 대해 코딩을 할 필요가 생겼다.

 

 를 구하는 것이므로 생각보다 간단하다고 생각했다.

하지만 값이 조금 커진다면.. 

예를 들어 1000C800 같은 것만 계산을 하더라도 부하는 물론 각각을 나누기 위한 Factorial을 계산하는 과정에서 unsigned long long (unsigned __int64) 에도 담지 못할 정도로 커진다.

크기와 부하 등의 문제가 생겨 쉬운 문제가 갑자기 어려워졌던 것이다.

찾다보니 아래 식을 이용하여 재귀로 풀면 된다는...

nCr = n-1Cr-1 + n-1Cr 

정말 이런 생각을 할 수 있을까 라는 생각이 들면서 회의감이 밀려들었다.

물론 고딩때 봤던 공식이지만 쓸때없어 그냥 지나쳤던 공식이다.

하지만 이런 공식을 알지 못하더라도 이걸 재귀로 짤 수 있다는 생각을 해내야 훌륭한 개발자가 될 수 있다고 생각한다;;