[백준/c++] 1003번: 피보나치 함수

 

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

1003번: 피보나치 함수

 

문제 요약

 

N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

 

 

---

 

 

여기서 fibonacci(1)이 호출되면 1, fibonacci(0)이 호출되면 0을 출력한다.

fibonacci(i)의 0과 1의 값을 차례대로 더해서 fibonacci(N)의 0과 1의 값을 출력하면 된다.

 

[0의 개수, 1의 개수]

fib(0) : [1, 0]

fib(1) : [0, 1]

fib(2) : [1, 1]

fib(3) : [1, 2]

fib(4) : [2, 3]

...

 

규칙이 보인다. 피보나치 수열 함수처럼 i-1, i-2를 인자로 한 재귀 함수를 돌리면 된다. 

여기서 초기값 fib(0), fib(1)은 고정시켜준다.

 

#include <iostream>
#define NUM 42
using namespace std;
int m, t;
long long dp[42][2];

void solution(){
    dp[0][0] = 1; dp[1][1] = 1;
    for(int i=2; i<=40; i++){
        dp[i][0] = dp[i-1][0] + dp[i-2][0];
        dp[i][1] = dp[i-1][1] + dp[i-2][1];
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> t;
    solution();
    while(t--){
        cin >> m;
        cout << dp[m][0] << ' ' << dp[m][1] << '\n';
    }
    return 0;
}

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!