greentea31's Note

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

풀이 과정

n번째 피보나치 수를 출력하는 문제이다.

피보나치 수를 재귀로 구하면 너무 시간이 오래 걸린다.

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

다음과 같은 점화식을 사용해 동적 계획법으로 문제를 해결하였다.

소스 코드

#include <iostream>
using namespace std;
long long d[91] = {0};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    d[0] = 0; d[1] = 1; d[2] = 1;

    for (int i = 3; i < 91; i++) {
        d[i] = d[i-1] + d[i-2];
    }

    cout << d[n];
    return 0;
}