Backjoon Online Judge
"2749번 : 피보나치 수 3" 문제입니다.
문제 링크 : https://www.acmicpc.net/problem/2749
피보나치 수 3번의 경우 N의 범위가 매우 크기에 일반적인 방법으로 피보나치 수를 구할 경우 long long int에서 저장 가능 한 범위를 초과하기 때문에 제대로 된 답이 나오지 않습니다.
피보나치 수의 특징으로 피보나치 수를 나눈 나머지는 주기성을 띄게 됩니다.
(=피사노 주기) 이를 활용하여 문제를 풀어가게 됩니다.
피사노 주기에서 길이가 1,000,000 일 경우, 주기 Period는 1,500,000이 됩니다.
- FIBO의 값을 일반적인 방식으로 구하되, 1,000,000이 넘는 경우 나머지만을 저장했습니다.
- FIBO의 값이 주기에 해당하는 값을 넘는 경우 값은 순환하므로 더 이상 구하지 않았습니다.
- n / 주기의 결과를 구해 n번째 값이 어느곳과 같은지를 확인하고 이를 출력했습니다.
코드는 C++로 작성하였습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #include <iostream> #define MOD 1000000 #define PERIOD 1500000 using namespace std; int main() { int fibo[PERIOD] = { 0,1 }; long long int n; cin >> n; for (int i = 2; i<PERIOD; i++) { fibo[i] = fibo[i - 1] + fibo[i - 2]; fibo[i] %= MOD; } cout << fibo[n % PERIOD] << '\n'; return 0; } | cs |
'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글
| 1149번 : RGB거리 (0) | 2018.04.01 |
|---|---|
| 1003번 : 피보나치 함수 (0) | 2018.04.01 |
| 2748번 : 피보나치 수 2 (0) | 2018.04.01 |
| 2747번 : 피보나치 수 (0) | 2018.04.01 |
| 5430번 : AC (0) | 2018.03.28 |