문제
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.
n=17일때 까지 피보나치 수를 써보면 다음과 같다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다.
예제 입력
1000
예제 출력
228875
힌트
출처
- 문제를 만든 사람: baekjoon
단순하게 1000000의 숫자로 나누는 문제가 아닌, '피사노 주기 알고리즘'을 알아야 되는 문제
피사노 주기는 피보나치 수를 K로 나눴을 때 그 나머지가 항상 주기를 가집니다.
예를 보시겠습니다.
이렇게 일정한 주기를 가지게 됩니다.
이 주기는 규칙을 가집니다
그렇다면 N = 10 이고 K = 3 / P = 8 이라고 하면
fibo(10) % 3 = fibo(10%8) % 3 -> 34 % 3 = fibo(2) % 3
-> 1 = 1
이렇게 같게 된다. 그렇다면 여기서 또 문제점이 생깁니다.
N 과 K는 그 값을 구할 수 있습니다. 그렇다면 주기 길이는 어떻게 구할까요?
(K : 나누는 수 / P : 주기 길이)
표로 나타내면 이렇게 됩니다. 그러면 이제 규칙을 찾아야하는데
딱 보이는 규칙은 없습니다.
하지만 위키백과사전에 보면 영어로 적힌 규칙이 있습니다(https://en.wikipedia.org/wiki/Pisano_period)
12를 구하는 것을 보게되면
12 = 3 * 4 이고 3의 피사노 주기 값과 4의 피사노 주기 값의 최소공배수를 구하면 됩니다.
즉, 3 피사노 주기 값은 8 이고 4 피사노 주기 값은 6이므로 최소공배수는 24가 됩니다.
12 = 2 * 6도 됩니다 3과 24의 최소공배수는 마찬가지로 24입니다.
이렇게 값을 구할 수 있지만 7이나 13와 같은 소수는 그 값을 구하기 힘듭니다.
위키백과사전에도 너무 어렵게 설명이 되어 있습니다.
그래서 조금 간단히 생각해보겠습니다.
다시 위로 올라가서 피사노 주기를 보겠습니다.
<피사노 주기>
3으로 나눴을 때를 예로 들겠습니다.
그렇다면 우리는 fibo(N) % 3 의 값을 구하는 것입니다.
이것은 다시 (fibo(N-2) + fibo(N-1)) % 3 이 되고 이 것은 다시 ((fibo(N-2) % 3) + (fibo(N-1) % 3)) % 3 이렇게
바꿀 수 있습니다.
조금 더 쉽게 숫자를 넣어보면
fibo(4)의 피사노 주기는 ((fibo(3) % 3) + (fibo(2) % 3)) % 3 = (2 + 1) % 3
= 0
import java.util.Scanner;
public class Beak2748 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] list = new long[n+1];
int mod = 1000000;
int period = pisano_period(mod);
list[0] = 0;
list[1] = 1;
for (int i = 2; i < list.length; i++) {
list[i] = list[i - 2] + list[i - 1];
list[i] %= mod;
}
System.out.println(list[n % period]);
}
public static int pisano_period(int m) {
int period = 0;
int number1 = 1, number2 = 1;
do {
int temp = number1;
number1 = number2;
number2 = (temp + number2) % m;
period++;
} while (!(number1 == 1 && number2 == 1));
return period;
}
}
출처: http://nackwon.tistory.com/52 [JIMMY]
'알고리즘(Java) > 피보나치 수' 카테고리의 다른 글
| 백준 1003번 피보나치 함수 (0) | 2017.12.05 |
|---|---|
| 백준 2748번 피보나치수 2 (0) | 2017.12.01 |
| 백준 2747번 피보나치 수 (0) | 2017.12.01 |