[정올 1053] 피보나치

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=332&sca=99 

JUNGOL

#include <stdio.h>

int fibo[100000], cycle;
const int CYCLE = 7;

bool CheckCycle(int idx) {
	for (int i = 0; i < CYCLE; i++) {
		if (fibo[i] != fibo[idx - CYCLE + i]) return false;
	}
	return true;
}

void SetFivo() {
	fibo[0] = 0, fibo[1] = fibo[2] = 1;

	for (int i = 2; i <= CYCLE; i++) {
		fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 10000;
	}
	for (int i = CYCLE + 1;; i++) {
		fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 10000;
		if (CheckCycle(i)) {
			cycle = i - CYCLE;
			break;
		}
	}
}

int main(void) {
	int n;
	SetFivo();
	while (1) {
		scanf("%d", &n);
		if (n == -1) break;
		printf("%d\n", fibo[n % cycle]);
	}
	return 0;
}