글 읽기 - 반례를 찾아주세요 (C++)

dmswl022329 3년 전 0

피보나치 숫자를 음수로 확장시키면

양수일때와 절대값이 같고
짝수일때만 마이너스가 붙는 규칙을 알아냈습니다

0 1 1 2 3 5 8 13 21 34 (N이 양수일때 0 1 2 3)

0 1 -1 2 -3 5 -8 13 -21 34 (N이 음수일때 0 -1 -2 -3 ...

그래서 코드를 짜보았는데 어디가 문제일까요

#include<bits/stdc++.h>
using namespace std;

int dp[1000001];

int main(){
    int N;
    cin >> N;
    dp[0]=0;
    dp[1]=1;
    for(int i=2;i<=1000000;i++){
        dp[i]=dp[i-1]%1000000000+dp[i-2]%1000000000;
    }
    if(N < 0){
        if((-N)%2==0)cout << "-1\n" << dp[-N];
        if((-N)%2!=0)cout << "1\n" << dp[-N];
    }else if(N>0){
        cout << "1\n" << dp[N];
    }else{
        cout << "0\n0"; 
    }
    return 0;
}

plan222 3년 전 1

dp[i]를 10억으로 나눠주지 않으니 마지막 100만번째는 10억으로 나눠져 있지 않겠네요

dmswl022329 3년 전 0

네 맞아요 ㅠㅠ 그걸 못보고 왜 안되는거지 반복했네요
감사합니다!

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

문제

문제

출처

ICPC

반례를 찾아주세요 (C++)

dmswl022329 3년 전 0

plan222 3년 전 1

dmswl022329 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말