(프로그래머스 c++)피보나치 수

피보나치 수열을 DP로 풀었다.

피보나치 수열에 관한 문제는 재귀, DP, 반복문을 사용하여 풀 수 있는데,

시간을 고려해야 하는 경우는 대부분 DP를 이용하면 풀 수 있다.

 

배열을 이용하여 F(n) = F(n - 1) + F(n - 2) 의 값을 저장한다.

반복문을 돌면서 계속해서 F(n - 1), F(n - 2)의 값을 가져오기 때문에

재귀보다 빠르게 풀 수 있다.

 

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    int num[100001] = {0, };
    num[0] = 0;
    num[1] = 1;
    
    for(int i = 2; i <= n; i++)
    {
        num[i] = (num[i - 1] + num[i - 2]) % 1234567;
    }
    return num[n];
}