[BOJ] 2749

https://www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

1. 아이디어 및 사용한 알고리즘이나 자료구조

dp로 무작정 풀기엔 n이 너무 크기 때문에 분할정복을 사용하려고 했다. 그래서 아래의 그림과 같이 간단한 행렬로 접근을 해보았다.

하지만 시간초과가 떴고 뭔가 이상했다. 1000000으로 나눈단 것이 이상해서 혹시나 반복이 되나 싶어서 피보나치 반복에 대해 검색해봤는데 역시나였다. 1000000으로 나눈 나머지의 피보나치는 주기가 1500000이었다. 결국 처음부터 dp로 1500000까지 구해준후 출력때 n을 1500000을 나눈 나머지번째의 수를 출력해주면 되는 것이었다. 

 

2. 코드

실패코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <memory.h>
#include <stack>
using namespace std;

#define mod 1000000

int ans[2][1];
int arr[2][2] = { 0, };

void mult()
{
	int ret[2][1] = { 0, };

	for (int i = 0; i < 2; i++)
	{
		for (int j = 0; j < 1; j++)
		{
			for (int x = 0; x < 2; x++)
				ret[i][j] += (arr[i][x] * ans[x][j]) % mod;
		}
	}

	ans[0][0] = ret[0][0];
	ans[0][1] = ret[0][1];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	
	int n;
	cin  >> n;

	arr[0][1] = 1;
	arr[1][0] = 1;
	arr[1][1] = 1;

	ans[0][0] = 1;
	ans[0][1] = 1;

	if (n == 1 || n == 2)
	{
		cout << 1 << "\n";
		return 0;
	}
	if (n >= 3)
	{
		n -= 2;
		while (n)
		{
			mult();
			n--;
		}
	}
	
	cout << ans[1][0] << "\n";
	
}

성공 코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <memory.h>
#include <stack>
using namespace std;

#define mod 1000000

int arr[1500010];

void mult()
{
	arr[0] = 0;
	arr[1] = 1;

	for (int i = 0; i < 1500000; i++)
		arr[i + 2] = (arr[i + 1] + arr[i]) % mod;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	
	long long n;
	cin  >> n;

	mult();
	cout << arr[n % 1500000] << "\n";
}

3. 마무리

피보나치에도 이런 신기한 주기가 있을 줄은 상상도 못했다. 너무 수학문제다. 시간 아까워...