[Programmers] 멀리 뛰기

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

프로그래머스

0. Headers

#include <vector>
using namespace std;

1. 알고리즘

 - 처음 이 문제를 보고 경우의 수를 모두 구해야하는 건가 싶었지만 처음부터 몇개의 가지수가 나오는지 확인

   - 1, 2, 3, 5, 8, 13 순으로 나오므로 먼가 규칙을 발견

     - 2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13으로 진행되므로 식을 생성

       - F[N] = F[N-1] + F[N-2]의 식이 생성됨

#include <vector>
using namespace std;

long long solution(int n) {
    vector<int> v(2001);
    v[0] = 1; v[1] = 1;
    for (int i = 2; i <= n; i++)
        v[i] = (v[i-1] + v[i-2]) % 1234567;
    return v[n];
}

2. 완성 코드

#include <vector>
using namespace std;

long long solution(int n) {
    vector<int> v(2001);
    v[0] = 1; v[1] = 1;
    for (int i = 2; i <= n; i++)
        v[i] = (v[i-1] + v[i-2]) % 1234567;
    return v[n];
}