백준 11401번
이항 계수 3, 분할정복
PYTHON
단순히 이항 계수를 구하는 것은 어렵지 않다.
nCk = n!/(n-k)!k! 을 계산하면 이항 계수를 구할 수 있다.
하지만 문제의 입력 범위가 1~4,000,000으로 매우 넓기 때문에 재귀로 해결하려고 할 때, 재귀 깊이 초과 오류가 발생하게 된다.
이 오류는 허용 가능한 깊이를 넘어서는 재귀 호출이 이루어진 경우를 말한다.
혼자서 이 문제를 해결하려고 할 때 오류를 발생시키지 않는 재귀식을 정의하는 것에 큰 어려움을 겪었다.
할 수 없이 검색을 통해 이 문제의 해결 방법을 알아냈다.
이 문제를 해결하기 위해서는 '페르마의 소정리'를 이용해야 했다.
페르마 소정리에 대한 자세한 정보는 아래의 링크에서 확인하자.
https://ko.wikipedia.org/wiki/%ED%8E%98%EB%A5%B4%EB%A7%88%EC%9D%98_%EC%86%8C%EC%A0%95%EB%A6%AC
소스 코드
문제 해답의 소스 코드는 아래와 같다.
power 함수는 거듭제곱의 값을 구하는 재귀 함수이다.
ex) n^4 = n^2 x n^2, n^5 = n^2 x n^2 x n
또한 팩토리얼 함수에서는 매 계산마다 p(1,000,000,007)로 나눈 나머지를 계산해서 저장한다.
이는 문제에서 요구한 사항이 p로 나눈 나머지를 구하는 것이기 때문이다.
나머지를 제외한 부분은 어차피 p의 배수이기 때문에 나중에 나머지를 구해도 똑같이 없어진다.
따라서 미리 나머지를 구해서 작은 계산을 하도록 한다.
Whiplash We Flash