[백준 C++]2749번: 피보나치 수 3 (행렬의 거듭제곱)

1.문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

2. Solved.ac 난이도

3. 활용 알고리즘:  행렬 곱셈

4. 틀린 이유: 컴파일 에러

---

시도1. (TLE)

원래 사용하던 DP나 재귀함수를 통해서 풀게된다면 무조건 시간초과가 난다. 수가 매우크다보니 mod 연산을 계속 수행해주는 것도 무척 부담이다. 따라서 행렬의 곱셈을 통해 계산하여야 했다.

 

 

시도2 (WA)

계속 load of null이 나왔다.

검색해보니 포인터가 선언될때 꼭 초기화가 필요한데, 이는 정적으로 선언된 배열이거나 동적할당을 받은 공간이어야 한다고 한다. 그런데 동적할당으로 해보았는데도 안되는 것 보니 그냥 포인터는 왠만하면 알고리즘에서 안쓰는 게 좋을 듯

#include<iostream>
using namespace std;
long long int* mult(long long int m1[][2], long long int m2[][2]){
	long long int result[4];
	result[0] = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % 1000000;
	result[1] = (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % 1000000;
	result[2] = (m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % 1000000;
	result[3] = (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % 1000000;
	return result;
}
	int main() {
		long long int n;
		cin >> n;
		
		long long int matrix[2][2] = { {1, 1}, {1, 0} };
		long long int result[2][2] = { {1, 0}, {0, 1} };
		long long int *val;
		for (long long int i = n; i >0; i/=2) {
			if (i%2==1) {
				val = mult(matrix, result);
				result[0][0] = val[0];
				result[0][1] = val[1];
				result[1][0] = val[2];
				result[1][1] = val[3];
			}
			val = mult(matrix, matrix);
			matrix[0][0] = val[0];
			matrix[0][1] = val[1];
			matrix[1][0] = val[2];
			matrix[1][1] = val[3];
		}
		cout << result[0][1] << endl;
		return 0;

 

 

최종 정답 코드

#include<iostream>

using namespace std;
long long int val[4];

void mult(long long int m1[][2], long long int m2[][2]){

	val[0] = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % 1000000;
	val[1] = (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % 1000000;
	val[2] = (m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % 1000000;
	val[3] = (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % 1000000;

}

	int main() {
		long long int n;
		cin >> n;
		
		long long int matrix[2][2] = { {1, 1}, {1, 0} };
		long long int result[2][2] = { {1, 0}, {0, 1} };

		for (long long int i = n; i >0; i/=2) {
			if (i%2==1) {
				mult(matrix, result);
				result[0][0] = val[0];
				result[0][1] = val[1];
				result[1][0] = val[2];
				result[1][1] = val[3];

				
			}
			mult(matrix, matrix);
			matrix[0][0] = val[0];
			matrix[0][1] = val[1];
			matrix[1][0] = val[2];
			matrix[1][1] = val[3];
		}
		cout << result[0][1] << endl;
		return 0;
	}