피보나치 함수

작성일 | In

[백준] 1003번 - 피보나치 함수

문제 링크

동적 계획법으로 쉽게 풀 수 있는 문제이다.
n번 째 피보나치 수가 0을 출력하는 횟수를 dp[n].first, 1을 출력하는 횟수를 dp[n].second 라고 할 때, 점화식은 아래와 같다.

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

pair<long long, long long> dp[41];
vector<int> src;

int main(void) {
    int t;
    scanf("%d", &t);
    src.resize(t);
    int maxN = 0;
    for(int i=0; i<t; ++i) {
        scanf(" %d", &src[i]);
        if(maxN < src[i]) maxN = src[i];
    }

    dp[0] = {1,0};
    dp[1] = {0,1};
    for(int i=2; i<=maxN; ++i)
        dp[i] = {dp[i-1].first + dp[i-2].first, dp[i-1].second + dp[i-2].second};

    for(int i=0; i<src.size(); ++i)
        printf("%lld %lld\n", dp[src[i]].first, dp[src[i]].second);
}
0%