피보나치 함수

문제

피보나치 함수

풀이

fibonacci(n)을 호출했을 때 이 출력되는 횟수를 , 이 출력되는 횟수를 이라 합시다. 그렇다면 아래 점화식을 통해 답을 구할 수 있습니다.

코드

Python

dp = [[0, 0] for _ in range(41)]
 
dp[0][0] = 1
dp[1][1] = 1
 
for i in range(2, 41):
    for j in range(2):
        dp[i][j] = dp[i - 1][j] + dp[i - 2][j]
 
for t in range(int(input())):
    n = int(input())
    print(dp[n][0], dp[n][1])

C++

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    vector<vector<int>> dp(41, vector<int>(2));
    dp[0][0] = 1;
    dp[1][1] = 1;
 
    for (int i = 2; i <= 40; i++)
        for (int j = 0; j < 2; j++)
            dp[i][j] = dp[i - 1][j] + dp[i - 2][j];
 
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << dp[n][0] << ' ' << dp[n][1] << '\n';
    }
 
    return 0;
}

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int dp[][] = new int[41][2];
        dp[0][0] = 1;
        dp[1][1] = 1;
 
        for (int i = 2; i <= 40; i++)
            for (int j = 0; j < 2; j++)
                dp[i][j] = dp[i - 1][j] + dp[i - 2][j];
 
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            bw.write(dp[n][0] + " " + dp[n][1] + "\n");
        }
 
        bw.close();
    }
}