프로그래머스 (Level 2) : 피보나치 수 /C++ /DP, 메모이제이션

문제

프로그래머스

 

피보나치 수 F(n) = F(n-1) + F(n-2)

input: 2<=n<=100,000 

return : n번째 피보나치 수 % 1234567

 

 

그냥 재귀함수로만 구현하면 틀리는 문제로 메모이제이션이 중요한 문제이다.

(실패이유 : 재귀함수 호출 수 초과)

 

 

메모이제이션 (memoization) :

한 번 계산한 결과는 저장, 이후 저장한 값으로 호출하여 재귀가 계속해서 호출되는 것을 방지

 

 

풀이

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int d[100001]; //전역=0초기화
int fibo(int n){
    if(n<=2) return 1;
    
    if(d[n]!=0) return d[n]%1234567; //메모이제이션
    else{
        d[n]=fibo(n-1)+fibo(n-2);
        return d[n]%1234567;
    }    
}

int solution(int n) {
    return fibo(n);
}