글 읽기 - [피보나치 함수]무엇이 문제인지 모르겠네요 ㅠㅠ

kso4013 8년 전 0

예시 입력에 대한 출력도 제대로 되고,

제가 임의로 입력한 값에 대해서도 정확히 반환하는것 같은데

계속 틀렸습니다. 라고 뜹니다..

다이나믹 프로그래밍을 제대로 사용한것 같은데..

가르침을 주시면 감사하겠습니다 ㅠ

#include<iostream>
#include<string.h>

using namespace std;

int cache[40][2];
int T; //test case;

int countzero(int);
int countone(int);

int main()
{
    cin>>T;
    int N[T];
    for(int i=0;i<T;i++)
        cin>>N[i];
    for(int i=0;i<T;i++)
    {
        memset(cache,-1,sizeof(int)*40*2); // to memoization
        cout<<countzero(N[i])<<" "<<countone(N[i])<<endl;
    }
    

    return 0;
}

int countzero(int n)
{

    int& ret=cache[n][0];
    if(ret!=-1) return ret;
  //  cout<<"ret : "<<ret<<endl;
    //base case
    ret=0;
    if(n==0){
        ret++; return ret;
    }else if(n==1){
        return ret;
    }else{
        return ret+=countzero(n-1)+countzero(n-2);
    }
}

int countone(int n)
{

    int& ret=cache[n][1];
    if(ret!=-1) return ret;
  //  cout<<"ret : "<<ret<<endl;
    //base case
    ret=0;
    if(n==0){
        return ret;
    }else if(n==1){
        ret++; return ret;
    }else{
        return ret+=countone(n-1)+countone(n-2);
    }
}

indioindio 8년 전 1

40 일 때 3, 0을 출력하네요

63245986 102334155

가 나와야 하는 데 말이죠.

문제에서 "N은 40보다 작거나 같은 자연수 또는 0이다."라고 했기 때문에 N = 40일 때도 값을 출력하셔야 해요!
적어 주신 소스코드에선 N = 40을 넣어버리면 배열 참조값을 벗어나 버리니 오답을 출력하게 됩니다.
int cache[40][2];와 memset(cache, -1, sizeof(int)*40*2);부분만 손 본다면 정답이 나올 거 같습니다.

여담이지만... 피보나치 수열의 재귀조건을 N ≥ -1까지로 확장하여, F(-1)도 사용할 수 있게 한다면, 반복문과 피보나치 수열 값을 저장하는 변수 두 개로도 풀 수 있을 거 같아요.

kso4013 8년 전 0

답변해주신 분들 모두 감사합니다!!! :)

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

문제

문제

출처

ICPC

[피보나치 함수]무엇이 문제인지 모르겠네요 ㅠㅠ

kso4013 8년 전 0

indioindio 8년 전 1

gallopsys 8년 전 1

kso4013 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말