#2749 피보나치 수 3

# 문제

 

# 풀이

앞의 9471 피사노 주기 문제에서 피보나치 수열의 성질을 배웠음

위 성질을 사용해 1,000,000으로 나눈 나머지는 1,500,000 주기를 가짐을 알 수 있음

1,500,000 개의 나머지를 모두 배열에 넣어놓고 주기에 맞는 나머지를 출력해주면 될 듯 하다!

 

#include <iostream>
#include <vector>
using namespace std;
int len = 1500000;

int main() {
	long long n;
	cin >> n;
	vector<long long> remainder;
	remainder.push_back(0); remainder.push_back(1); remainder.push_back(1);
	for (int i = 3; i < len; i++) {
		remainder.push_back((remainder.at(i - 1) + remainder.at(i - 2)) % 1000000);
	}
	cout << remainder.at(n % len);
}

 

문제를 풀면서 %1000000 부분과 %1500000을 해줘야 하는 부분이 헷갈렸다

전자의 경우는 문제에서 1,000,000으로 나눈 나머지를 물었기 때문에 그런 것이고

후자의 경우는 배열의 크기가 1,500,000이므로 입력받은 n이 배열에서 어느 인덱스를 가리키는 지에 대해 찾기 위한 것임

 

다른 사람 코드를 찾아보니

굳이 벡터를 쓸 필요가 없어보이던데

메모리 할당부분에서 정적배열이 더 좋아보인다,,? (아마)