자바 [Programmers] 2단계 - 멀리 뛰기

📝문제 설명

 

- 경우의 수를 보니 DP 문제인것 같아서 경우의 수를 구해봤다

칸	경우의 수	가지
1칸	1	1가지
2칸	1+1 2	2가지
3칸	1+1+1 2+1 1+2	3가지
4칸	1+1+1+1 2+1+1 1+2+1 1+1+2 2+2	5가지
5칸	1+1+1+1+1 2+1+1+1 1+2+1+1 1+1+2+1 1+1+1+2 1+2+2 2+1+2 2+2+1	8가지

 

뭔가 규칙이 보이는 것 같다.

DP[N] = DP[N-1] + DP[N-2]의 공식이 보인다

바로 ㄱㄱ

---

📢입출력 예시

 

---

✏️문제 풀이

class Solution {
    public long solution(int n) {
        long[] dp = new long[2001];
        
        dp[1] = 1;
        dp[2] = 2;
        
        for(int i=3; i<2001; i++){
            dp[i] = (dp[i-1] + dp[i-2]) % 1234567;
        }

        return dp[n];
    }
}

---