[프로그래머스] 피보나치 수 - C++

문제

• 프로그래머스 피보나치 수
• https://programmers.co.kr/learn/courses/30/lessons/12945

풀이

메모이제이션을 이용하면 간단하게 풀 수 있다.

F(n) = F(n-1) + F(n-2) 수식을 그대로 적용하여 반복문을 통해 피보나치 수열을 구하면 된다.

코드

#include <string>
#include <vector>

using namespace std;
int memo[100000];
int fibo(int n){
    memo[0] = 0;
    memo[1]= 1;
    for(int i=2;i<=n;i++){
        memo[i] = (memo[i-1]%1234567) +(memo[i-2]%1234567);
    }
    return memo[n];
}
int solution(int n) {
    int answer = 0;
    answer = fibo(n)%1234567;
    return answer;
}