백준 11444 - 피보나치 수 6(C++)

문제 링크입니다. https://www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

행렬과 분할 정복을 이용해 푸는 문제입니다.

 

이 문제를 풀기 전에 피노나치 수열을 행렬로서 나타낼 수 있다는 것을 알아야합니다.

피보나치의 행렬 표현

값 확인

더 알아보고 싶다면 해당 링크를 확인해주세요 https://jow1025.tistory.com/101

 

 

위의 정보를 통해서 피보나치가 행렬로 계산이 가능함을 확인할 수 있었습니다.

또한 행렬의 곱셈도 어떤 방식인지 확인할 수 있었습니다.

 

따라서 N번째 피보나치 수열을 구할 때, N값에 따라서 나눠서 계산해 주면 됩니다.

N이 짝수일 경우 2로 나눠서 다시 구해주면 되고, N이 홀수일 경우 N-1 + 1로 나누어서 짝수를 만들어 주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#define div 1000000007

using namespace std;

typedef struct Fi {
	long long int Data[2][2];
}Fi;
long long int N;

Fi multiple(Fi a, Fi b) {
	Fi multi;
	multi.Data[0][0] = (a.Data[0][0] * b.Data[0][0] + a.Data[0][1] * b.Data[1][0]) % div;
	multi.Data[0][1] = (a.Data[0][0] * b.Data[0][1] + a.Data[0][1] * b.Data[1][1]) % div;
	multi.Data[1][0] = (a.Data[1][0] * b.Data[0][0] + a.Data[1][1] * b.Data[1][0]) % div;
	multi.Data[1][1] = (a.Data[1][0] * b.Data[0][1] + a.Data[1][1] * b.Data[1][1]) % div;
	return multi;
}

Fi Fibonacci(Fi x, long long int num) {
	if (num > 1) {
		x = Fibonacci(x, num / 2);
		x = multiple(x, x);
		if (num % 2 == 1) {
			Fi Base;
			Base.Data[0][0] = 1, Base.Data[0][1] = 1;
			Base.Data[1][0] = 1, Base.Data[1][1] = 0;
			x = multiple(x, Base);
		}
	}
	return x;
}

void solve() {
	Fi start;
	start.Data[0][0] = 1, start.Data[0][1] = 1;
	start.Data[1][0] = 1, start.Data[1][1] = 0;
	start = Fibonacci(start, N);
	cout << start.Data[0][1];
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요