C++ / 프로그래머스 / 피보나치 수

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12945? 

프로그래머스

문제풀이

DP를 이용, 피보나치 수의 성질을 이용하여 DP[idx] = DP[idx -1] + DP[idx - 2]를 n까지 구한다.

문제에 나온 1234567로 나눈 나머지를 다시 저장한다.

 

코드

#include <string>
#include <vector>
#define DIV 1234567
using namespace std;

int solution(int n) {
    int answer(0), idx(0);
    vector<int>DP(n + 1, 0);
    
    DP[1] = 1;
    DP[2] = 1;
    
    for (idx = 3; idx <= n; ++idx) {
        DP[idx] = (DP[idx - 1] + DP[idx - 2]) % DIV;
    }

    return DP[n];
}