[BOJ] #10870 - 피보나치 수 5

👻 피보나치 수 5

👉🏻 문제 보러가기 👈🏻

---

🌱 문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

• 시간 제한 : 1초
• 메모리 제한 : 256 MB

---

🌱 입력

첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.

---

🌱 출력

첫째 줄에 n번째 피보나치 수를 출력한다.

---

🌱 예제

---

🪐 입출력 1

• 입력

  10
  

• 출력

  55
  

---

👻 풀이

#include <bits/stdc++.h>
using namespace std;

int cache[21];
int Fibonacci(int n)
{
    int& ret = cache[n];
    if (n <= 0)
        ret = 0;

    if (n == 1)
        ret = 1;

    if (ret != -1)
        return ret;

    return ret = Fibonacci(n - 1) + Fibonacci(n - 2);
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 피보나치 수
    ::memset(cache, -1, sizeof(cache));
    int n;
    cin >> n;
    cout << Fibonacci(n);
    return 0;
}

• 시간 : 0 ms
• 메모리 : 2020 KB

---

👻 글을 마치며

동적 계획법에 대해 간단하게 알아보고 개념을 이해한 후 바로 풀어본 알고리즘 예제 문제이다. 점화식만 알면 쉽게 작성할 수 있다는 생각과 함께 알고리즘을 구현해보니 정말 어렵지 않게 정확도와 효율성 모두 잡을 수 있는 코드를 만들 수 있었다. 그리고 알고리즘 문제들을 어느정도 풀다보니 적응이 된건지 코드를 짜거나 공부할 때 어떻게 코드를 구현하는 것이 효과가 있을까 하는 생각을 많이 하게 된다. 좋은 발전이라고 생각한다. ☺

---

소스코드 보러가기