백준 15624번: 피보나치 수 7 (C++)

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

15624번: 피보나치 수 7

---

Solved By: DP, map

 

n의 범위가 [1, 1,000,000]으로 너무 큽니다. 배열을 선언할 수도 없기 때문에 map을 사용하여 dp를 돌려봤습니다.

#include <iostream>
#include <map>
#define MOD 1000000007
using namespace std;

int n;
map<int, int> m;

int fibo(int n){
    if(n == 0) return 0;
    else if(n == 1 || n == 2) return 1;
    else{
        if(!m[n]) return m[n] = (fibo(n - 1) % MOD + fibo(n - 2) % MOD) % MOD;
        else return m[n];
    }
}


int main(){
    cin >> n;
    cout << fibo(n);
    return 0;
}