Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 알고리즘
- 북리뷰
- DP
- 오에스
- 백준
- cs
- 그래프
- 문제풀이
- bfs
- 너비우선탐색
- 코테
- 스택
- 컴퓨터공학과
- 브루트포스
- 컴공
- coding
- 정석학술정보관
- 정석
- 개발
- 코딩
- 구현
- 자료구조
- OS
- 오퍼레이팅시스템
- Operating System
- vector
- Stack
- Computer science
- c++
- 컴공과
Archives
- Today
- Total
Little Jay
[C++] 백준 2749번 피보나치 수 3 본문
앞의 글을 참조해야 한다
피사노 주기를 통해서 어떤 피보나치 수를 1000000으로 나눈 주기는 1500000이다.
따라서 n에 어떤 수가 들어오더라도
n mod 1500000의 값만 찾으면 된다.
또한 미리 피보나치 배열을 하나 만들어 놓으면 메모리 누수가 적을 것이다.
#include <iostream>
#include <vector>
using namespace std;
long long a[1500010];
void fibo() {
a[0] = 0;
a[1] = 1;
for (int i = 0; i < 1500000; i++) {
a[i + 2] = (a[i + 1] + a[i]) % 1000000;
}
}
int main() {
long long n;
cin >> n;
fibo();
cout << a[n % 1500000] << "\n";
return 0;
}
'알고리즘 > BOJ' 카테고리의 다른 글
[C++] 백준 17608번 막대기 (0) | 2021.07.30 |
---|---|
[C++] 백준 1436번 영화감독 숌 (0) | 2021.07.23 |
[C++] 백준 9471번 피사노 주기 (0) | 2021.07.23 |
[C++] 백준 1920 수 찾기 (0) | 2021.07.18 |
[C++] 백준 15829번 Hashing (0) | 2021.07.18 |
Comments