[백준] 11444번 피보나치수 6 C++ 풀이

---

알고리즘 분류

• 수학
• 분할정복

---

문제 설명

피보나치 수는 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번째 피보나치 수를 구하는 프로그램을 작성하시오.

---

입력 설명

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

---

출력 설명

첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

---

예제 입력

1000

---

예제 출력

517691607

---

아이디어

기존 피보나치를 풀던 메모이제이션 방법으로는 n의 최댓값이 너무 커서 계산이 힘들다.

그래서 아래의 도가뉴 항등식을 짝수일 때와 홀수일 때로 구분하여 전개해서 해결 가능하다.

 

 

짝수일 때는 Fn = F(n/2) (F(n/2+1) + F(n/2-1))이며

홀수일 때는 Fn = F((n+1)/2)^2 + F((n-1)/2)^2이다.

---

알고리즘

map에 key가 0일 때의 value 0과

key가 1일 때의 value 1을 삽입한다.

이후 fib 함수 내에서 map에 n이 존재하면 해당 n을 출력한다.

n이 존재하지 않는다면 홀수인지 짝수인지 판별 후 위의 도가뉴 항등식의 전개식을 사용해서 계산하여

map에 계산 값을 삽입하고 그 값을 return 한다.

 

---

코드

#include <iostream>
#include <map>
using namespace std;
map<long long, long long> mp;
#define MOD 1000000007
long long fib(long long num)
{
    if (mp.find(num) != mp.end())
        return mp[num];
    if (num % 2 == 0)
        return mp[num] = (fib(num / 2) * (fib(num / 2 + 1) + fib(num / 2 - 1))) % MOD;
    else
        return mp[num] = (fib((num + 1) / 2) * fib((num + 1) / 2) + fib((num - 1) / 2) * fib((num - 1) / 2)) % MOD;
}
int main()
{
    long long n;
    cin >> n;
    mp.insert({0, 0});
    mp.insert({1, 1});
    cout<<fib(n);
    return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/11444

처음 시도한 건 bottom-up 방식의 단순한 풀이였다.

시간이 너무 오래 걸린다고 생각하여 메모이제이션을 이용한 top-down 방식을 변경하였다.

그래도 n의 최댓값이 너무 커서 초과가 발생하였다.

그래서 인터넷에 검색하다가 나온 게 도가뉴 항등식이었다.

이를 이용하니까 빠르게 해결 가능했다.

그리고 기존에는 메모이제이션을 이용할 때 vector만 사용했었는데 map을 사용하니까 더 좋은 것 같다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!