2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 읽기 일단 피보나치를 푸는 내가 아는 가장 간단한 방법.. DP.. 그거 말고는 생각이 나지 않았는데, 문제에서 주어지는 N의 크기는 엄청났다. 무려 10의 18승..!! 저번에 풀었던 power의 분할 정복 처럼 로그를 씌우지 않고는 불가능한 거 아닌가? 생각이 들면서 전혀 감이 잡히지 않았고, DP로 코드를 한 번 짜봤지만 당연하게도 N의 최대 범위를 넣으니 응답이 없었다.. 그래서 질문 게시판을 참고했다. 피보나치 수를 구하는 여러가지 방법 피보나치 수는 다음과 같이 정의되는 수열입니다. $F_0 = 0$ $F_1 = 1$ $F_n..

11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 읽기 문제는 일단 조합을 구하는 문제이다. 문제는 N이 매우 크다는 것.. 수식 외에 조합을 어떻게 빨리 구할 수 있을 지를 먼저 생각했다. 첫 번째로 떠오른 것은 DP이다. C(n, k) = C(n-1, k-1) + C(n-1, k) 위 식이 떠올랐고, DP가 떠올랐다. 하지만 N이 4백만이므로, 400만 X 400만 하면 메모리가 터진다. 혹시나 해서 해봤지만 역시나 터졌다. 수식으로 접근 C(n, k) = n! / (k! * (n-k)!) 위 식을 계산하여 풀 수 있을까 했는..