[백준] 2747번 피보나치 수

문제

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include<iostream>
constexpr int MAX = 45;
//동적 계획법으로 풀어보자
 
int main() {
    int number;
    int Fibonacci[MAX];
    Fibonacci[0] = 0;
    Fibonacci[1] = 1;
    std::cin >> number;
 
    for (int i = 2; i <= number; ++i) {
        Fibonacci[i]=Fibonacci[i - 2] + Fibonacci[i - 1];
    }
    std::cout << Fibonacci[number] << "\n";
 
}
 

동적 계획법으로 푼 방법

1
2
3
4
5
6
7
8
9
10
11
12
13

#include<iostream>
 
// 피보나치 n= (n-2)+(n-1)
int Fibonacci(int number) {
    if (number <= 1)return number;
    return Fibonacci(number - 2) + Fibonacci(number - 1);
}
 
int main() {
    int number;
    std::cin >> number;
    std::cout << Fibonacci(number) << "\n";
}
 