프로그래머스 연습문제 멀리 뛰기 [JAVA] - 22년 10월 2일

n칸을 뛰어야 할때 나올 수 있는 경우의 수

경우의 수

1. n-1칸 + 1칸
2. n-2칸 + 1칸 + 1칸 (2칸을 1칸씩 나눠서 뜀)
3. n-2칸 + 2칸 (한번에 2칸)

그러므로 n칸을 뛸때 필요한 경우의 수 점화식을 세우면

n칸 = (n-1칸 경우의 수) + (n-2칸 경우의 수)*2

근데 여기서 고려해야 하는게 n-2칸 + 1칸 + 1칸
과 n-1칸 + 1칸 의 내용이 겹친다.

그러므로 중복을 제외하고 다시 점화식을 세우면

n칸 = (n-1칸 경우의 수) + (n-2칸 경우의 수)

class Solution {
    public long solution(int n) {
        long[] memo = new long[2001];
        memo[1] = 1;
        memo[2] = 2;

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

        return memo[n];
    }
}