글 읽기 - 궁금한점이있습니다.[정답 스포 주의]

johyesong8686 3년 전 0

피보나치의 주기를 활용하여 푸는 방법을 알게되었습니다. 다만

//2의 풀이로 메모리를 아끼는 방법은 왜 안되는 지 알수 있을까요 ?

//1
#include <iostream>
#define MOD 1000000
using namespace std;

int main() {
    long long n;
    cin >> n;
   
    int p=15*MOD/10; //피보나치의 주기
    int fibo[p+1]={0,1};
    for(int i=2; i<p;i++){ //p까지 반복
        fibo[i]=fibo[i-1]+fibo[i-2];
        fibo[i]%=MOD;
    }
    cout <<fibo[n%p];

    return 0;
}

//2

#include <iostream>
#define MOD 1000000
using namespace std;

int main() {
    long long n;
    cin >> n;
   
    int p=15*MOD/10; //피보나치의 주기
    int fibo[3]={0,1};
    for(int i=2; i<p;i++){ //p까지 반복
        fibo[i%3]=fibo[(i-1)%3]+fibo[(i-2)%3];
        fibo[i%3]%=MOD;
    }
    cout <<fibo[n%p%3];

    return 0;
}

shg9411 3년 전 1

말씀하신 것 처럼 주기가 있는데

p만큼 반복문을 돌린다면 크기 3의 배열에 주기를 모두 저장하실 수는 없겠죠.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

궁금한점이있습니다.[정답 스포 주의]

johyesong8686 3년 전 0

shg9411 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말