Development Artist

백준 단계별 풀기에서 분할정복 다섯 번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 절대 단순한 문제가 아니다. 설계를 어떻게 하느냐에 따라 연산의 성능이 확연히 차이가 난다. 방법은 3가지가 있다. 1. 점화식을 이용한 방법 -> O(N^2)으로 시간 초과 2. 이항계수의 정의를 활용한 방법 2.1. 확장 유클리드(호제법) 2.2. 페르마 소정리 우리는 확장 유클리드 알고리즘과 페르마 소정리를 이용하고자 한다. (실제 백준 추천 알고리즘) 일..