Lv.2 / 멀리 뛰기

문제

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

프로그래머스

---

코드

#include <string>
#include <vector>

#define MAX 2001
#define MOD 1234567

using namespace std;

int solution(int n) {
    int dp[MAX] = { 0, };

    dp[1] = 1;
    dp[2] = 2;

    for(int i=3; i<=n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
    }

    return dp[n] % MOD;
}

---

풀이

1칸 혹은 2칸까지만 뛸 수 있기 때문에 n 칸에서 경우의 수는 n - 1 칸까지 뛰는 경우의 수에 1칸 뛰는 것과 n - 2 칸까지 뛰는 경우의 수에 2칸 뛰는 경우가 포함된다.

n 칸까지의 경우의 수를 F(n) 이라 할 때, F(n) = F(n-1) + F(n-2) 가 된다.
즉, 피보나치의 수와 같다.