November 9, 2020
BOJ 2749 문제 설명 문제: 백준 2749 이 문제는 아주 큰 피보나치 수를 구하는 문제입니다. 주어진 수 N에 대해 N번째 피보나치 수를 어떤 수로 나눈 나머지를 구하면 되는 문제입니다. 이 문제는 피보나치 수를 구하기만 하면 되기 때문에 굉장히 쉬워 보이지만 N이 $10^{18}$이하의 자연수라는 점이 문제가 됩니다. $O(N)$ 시간 복잡도로는 절대 풀 수 없는 문제입니다.
사전 지식 이 포스트에서는 N번째 피보나치 수를 구하는 방법에 대해 말해보고자 합니다! 그전에 피보나치 수열에 대해 간단히 살펴보죠.
read more