취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17840번 문제인 피보나치 음악이다.
문제는 아래 링크를 확인하자.

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

M의 제한이 1,000 이하인 것에 주목하자.

피보나치 수를 구하는 점화식을 관찰하면 새로운 항은 이전 두 항의 쌍에 의해 결정되는 것을 알 수 있다. 이러한 두 항의 쌍은 M의 제한이 1,000이므로 1,000*1,000 = 1,000,000가지밖에 존재하지 않게 된다.

따라서 많아봐야 100만개의 항을 구하면 피보나치 점화식은 어느 순간서부터 주기적으로 반복하는 모습을 보이게 될 것이다.

피보나치 수를 M으로 나눈 수열의 주기는 항상 초항을 포함하여 구성된다는 사실은 잘 알려져있다. 이 사실에 대해 더 알고싶다면 피사노 주기(Pisano period)에 대하여 조사해보자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

int M, Q;
string s = "";

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> Q >> M;

	int x = 1, y = 1;
	while (!(x == 0 && y == 1)) {
		s += to_string(x);
		int tmp = (x + y) % M;
		x = y; y = tmp;
	}

	s += "0";

	ll MOD = s.length();
	while (Q--) {
		ll q; cin >> q;
		cout << s[(q - 1) % MOD] << '\n';
	}
}