[백준/c++] BOJ 1003 - 피보나치 함수

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

1003번: 피보나치 함수

 

문제 설명

다음 소스는 N번째 피보나치 수를 구하는 c++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구한다.

해결

a. n = 0

0: 1, 1: 0

 

b. n == 1

0: 0, 1: 1

 

c. n == 2

0: 1, 1: 1

 

d. n == 3

0: 1, 1: 2

 

위를 보면 단순한 규칙성을 찾을 수 있다.

dp[n] = dp[n - 1] + dp[n - 2]

 

나는 pair를 이용하여 0과 1을 따로 생각해 주었지만, 하나로 묶어도 풀 수 있다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
#define INF 1e9
using namespace std;

int n;
pair<int, int> dp[41];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    dp[0] = { 1, 0 };
    dp[1] = { 0, 1 };

    int remember = 1;
    cin >> n;
    while (n--) {
        int m;
        cin >> m;
        if (remember < m) {
            for (int i = remember + 1; i <= m; i++)
                dp[i] = { dp[i - 1].x + dp[i - 2].x, dp[i - 1].y + dp[i - 2].y };
            remember = m;
        }

        cout << dp[m].x << " " << dp[m].y << "\n";
    }
}