[C++][알고리즘] 백준 1003번 피보나치 함수

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

solved.ac 실버 3난이도 문제.

당연히 맞을 줄 알았는데 틀려서 당황.

 

알고보니 N이 40보다 작거나 "같은" 건데 그냥 <40 이라고 생각했다 멍청하게...

 

#include <iostream>
#define MAX_N 41
using namespace std;

struct list{
    int zeros;
    int ones;
};

int main(){
    ios_base::sync_with_stdio(0);
    int T;
    int N;
    cin >> T;
    struct list pibonacci[MAX_N];
    pibonacci[0].ones = 0;
    pibonacci[0].zeros = 1;
    pibonacci[1].ones = 1;
    pibonacci[1].zeros = 0;

    for(int i=2; i<MAX_N; i++)
    {
        pibonacci[i] = {pibonacci[i-1].zeros+pibonacci[i-2].zeros, pibonacci[i-1].ones + pibonacci[i-2].ones};
    }

    for(int i=0; i<T; i++)
    {
        cin >> N;
        printf("%d %d\n",pibonacci[N].zeros,pibonacci[N].ones);
    }
    return 0;
}

구조체를 이용해서 0과 1이 호출된 횟수를 각 숫자별로 기록했다.

처음엔 scanf printf 를 사용했다. (시간이 더 줄을거라 생각해서)

근데 한번 틀려서 stdin stdout 이 문제인가; 싶어서 저렇게 애매하게 고쳐놨다.

 

구조체 = { 멤버, 멤버, 멤버 } 의 형식으로,

초기화 및 할당하는 것은 g++11 버전 이상에서만 가능한 문법이다.

 

일부 코딩테스트에서는 사용할 수 없을 수도 있다.

 

문제 분류 : 다이나믹 프로그래밍