[백준] 2749 피보나치 수 3

문제링크: www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

문제에서 엄청 큰 n에 대하여 피보나치 수를 구하라 한다. 이 때 100만으로 나눈 나머지의 값이다.

100만으로 나눈 나머지라는 문장을 본 순간

100만으로 나눈 나머지 값이 어떤 연속된 두 수는 이전에 연속된 두 수와 같을 것이라 생각했다.

코드에서 보면 init 함수가 그러하고 그 싸이클 크기를 cycleLen이라는 변수에 저장했다.

출력 해보니 15만인가 150만인가 하는 수가 나온다. 기억은 안난다. 또, 그 주기의 시작 값이 (0,1)이라는 것도 알았다.

어쨌든 100만으로 나눈 나머지 값을 가지는 피보나치 수는 cycleLen을 주기로 같고 시작 값이 0이므로 쉽게 정답을 도출했다.

 

import java.io.*;
import java.util.*;
public class Main {
	public static int cycleLen;
	public static final int max_len = 10000000;
	public static final int MOD = 1000000;
	public static int []dp;
	public static int []position;
	public static void init() {
		dp[1] = 1;
		position[1] = 1;
		for(int i=2;i<max_len;i++) {
			dp[i] = (dp[i-2]+dp[i-1]) %MOD;
			if((position[dp[i]]-position[dp[i-1]])==1) {
				cycleLen = (i-1) - position[dp[i-1]];
				break;
			}
			if(position[dp[i]]==-1)
				position[dp[i]] = i;
		}
	}
	public static void main(String[] args) throws Exception {
		dp = new int[max_len];
		position = new int[1000001];
		for(int i=0;i<=1000000;i++) {
			position[i] = -1;
		}
		position[0] = 0;
		init();
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		n %=cycleLen;
		System.out.println(dp[(int)n]);
	}

}