글 읽기 - 95% 틀렸습니다

bangu 7년 전 0

95% 까지 채점하다가 틀렸다고 나오네요..

혹시 간과할만한 테스트 케이스가 있을까요??

#include <iostream>
#include <map>
using namespace std;

#define DIVIDE 100000000000000LL

class Fibonacci{
public:
    
    Fibonacci(){
        A[1] = 1;
        A[2] = 1;
        A[3] = 2;
        A[4] = 3;
        A[5] = 5;
        
        B[1] = 1;
        B[2] = 3;
        B[3] = 4;
        B[4] = 7;
        B[5] = 11;
        
    }
    
    //N번째 피보나치 값을 얻어온다.
    long long getFibonacci(long long N){
        if(N == 0)
            return 0;
        
        return getA(N);
    }
    
private:
    map<long long, long long> A, B;
    
    
    //A 수열의 N번지 값을 얻어온다.
    long long getA(long long N){
        
        //만약에 N번째 값이 정의되어 있지 않다면 정의해준다.
        if(A[N] == 0){
            if(N % 2 == 0){
                A[N] = (getA(N/2) * getB(N/2)) % DIVIDE;
                B[N] = (getB(N/2) * getB(N/2)) % DIVIDE;
                if(N/2 % 2 == 0){
                    B[N] -= 2;
                    B[N] %= DIVIDE;
                }else{
                    B[N] += 2;
                    B[N] %= DIVIDE;
                }
            }else{
                A[N] = (getA(N/2 + 1) * getB(N/2)) % DIVIDE;
                if(N/2 % 2 == 0){
                    A[N] -= 1;
                    A[N] %= DIVIDE;
                }else{
                    A[N] += 1;
                    A[N] %= DIVIDE;
                }
                B[N] = (getB(N/2 + 1) * getB(N/2)) % DIVIDE;
                if(N/2 % 2 == 0){
                    B[N] -= 1;
                    B[N] %= DIVIDE;
                }else{
                    B[N] += 1;
                    B[N] %= DIVIDE;
                }
            }
        }
        
        return A[N];
    }
    
    //B 수열의 N번지 값을 얻어온다.
    long long getB(long long N){
        
        if(B[N] == 0){
            getA(N);
        }
        
        return B[N];
    }

};

int main(){
    
    int T;
    cin >> T;
    
    Fibonacci fibo;
    
    while(T--){
        int N;
        
        cin >> N;
        
        //N보다 크지 않은 최대의 피보나치 수를 찾는다.
        //해당 피보나치 수부터 다시 밑으로 내려가면서 딱 떨어지는 피보나치의 합을 구한다.
        int MaxNum = 1;
        
        while(fibo.getFibonacci(MaxNum + 1) < N)
            MaxNum++;
        
        int FiboList[1000] = {0, };
        int top = 0;
        for(int i = MaxNum; i > 0; i--){
            //만약 N보다 피보나치 수가 작으면 피보나치 수만큼 빼주고, 그 수를 배열에 넣어준다.
            if( fibo.getFibonacci(i) <= N ){
                N -= fibo.getFibonacci(i);
                FiboList[top] = fibo.getFibonacci(i);
                top++;
                
                if(N == 0)
                    break;
            }
        }
        
        for(int i = top - 1; i >= 0; i--){
            printf("%d ",FiboList[i]);
        }
        printf("\n");
        
    }
    

    
    
    return 0;
}

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

문제

문제

출처

ICPC

95% 틀렸습니다

bangu 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말