백준 1003 피보나치 함수 [C++]

작성일 | In |

Problem : 피보나치 함수

유형 : DP

문제 해석

  • 피보나치 수를 재귀적으로 구할때 0,1이 호출되는 개수를 구하라.

해결 전략

  • N이 40이다.
  • 나이브하게 재귀적으로 구현하면 TLE가 발생한다.
    • 2^40 의 복잡도가 나온다.
  • DP로 O(N)에 해결한다.
    • 0과 1이 호출된것을 메모이제이션 한다.

구현

  • DP[N] = DP[N-1] + DP[N-2]

피드백

  • 없음

주의할 점

  • 재귀적으로 솔루션을 내기전에는 항상 시간복잡도를 고려해보기

코드

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

pii fiboDP[42] = { {1,0}, {0,1} };

void solve() {
    for (int i = 2; i <= 40; ++i) {
        fiboDP[i].first = fiboDP[i - 1].first + fiboDP[i - 2].first;
        fiboDP[i].second = fiboDP[i - 1].second + fiboDP[i - 2].second;
    }
    int t;
    cin >> t;
    while (t--) {
        int n;  cin >> n;
        cout << fiboDP[n].first << " " << fiboDP[n].second << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);
    solve();

    return 0;
}

피드백

  • 없음