[BOJ] 2749번 : 피보나치 수 3

2749번: 피보나치 수 3

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

• 접근

보통 피보나치 문제를 접근할 때에는 divide and conquer 또는 DP로 접근한다. n이 매우 작은 경우(BOJ 2747 참조)에는 재귀로 풀어도 풀 수 있다. 시간복잡도가 O(2^N)이기 때문이다.

그보다 n이 조금 더 커진다면 DP로 풀 수 있다. 이 경우 time complexity가 O(N)이므로 N이 대략 2억 언저리인 경우까지도 해결이 가능하다.

이 문제는 다르다. n의 upper bound가 1e18이다. 이런 경우에는 O(N)으로 풀 수 없다. O(logN)의 시간복잡도로 풀겠다는 생각을 해야 한다.

이 문제는 행렬곱 문제로 치환할 수 있다. 귀중한 통찰을 얻은 블로그가 있다. 이 문단의 설명은 이 블로그의 글로 갈음한다.

백준 [2749] 피보나치 수 3

백준 [2749] 피보나치 수 3 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로

egg-money.tistory.com

나머지는 구현이다. 행렬 제곱의 O(logN) 구현에 대해서는 BOJ 10830 : 행렬 제곱을 참조하면 좋다.

10830번: 행렬 제곱

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

전체 코드는 내 github에서 확인할 수 있다.

GitHub - Jordano-Jackson/PS: Problem solving

Problem solving. Contribute to Jordano-Jackson/PS development by creating an account on GitHub.

github.com