[백준 / SILVER 3] 피보나치 함수

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

1003번: 피보나치 함수

문제 접근법

• N 번째 피보나치 수를 구하는 함수를 실행했을 때 0과 1이 출력되는 횟수를 구하는 문제입니다.
• 문제를 풀기 위해 0과 1이 출력 되는 규칙을 찾아야 합니다.

0의 횟수와 1의 횟수가 피보나치 수를 이룬다는 규칙을 찾을수 있었습니다!

피보나치 수를 배열에 저장하고 이를 조건에 맞추어 출력해주면 문제를 해결할 수 있습니다.

 

아래는 코드입니다.

#include <iostream>
 
using namespace std;
 
int dp[41];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    
    dp[0] = 1;
    dp[1] = 1;
 
    for (int i = 2; i < 41; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
 
    while (t--)
    {
        int num;
        cin >> num;
        
        if (num == 0)
            cout << "1 0\n";
        else if (num == 1)
            cout << "0 1\n";
        else
            cout << dp[num - 2] << " " << dp[num - 1] << "\n";
    }
 
    return 0;
}