[프로그래머스, 12914] 멀리 뛰기 (java)

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

프로그래머스

728x90

---

메모리: 80 MB, 시간: 0.21 ms

사용 알고리즘: 다이나믹 프로그래밍

 

i칸으로 이동하는 방법은

i - 1칸에서 1칸 뛰는 방법과

i - 2칸에서 2칸 뛰는 방법이 있다.

dp[i] = dp[i - 1] + dp[i - 2]

class Solution {
    
    static final int MOD = 1_234_567;
    
    public long solution(int n) {
        
        if(n == 1) return 1;
        else if(n == 2) return 2;
        
        long[] dp = new long[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        
        for(int i = 3; i <= n; i++) {
            dp[i] += dp[i - 1];
            dp[i] += dp[i - 2];
            dp[i] %= MOD;
        }
        
        long answer = dp[n];
        return answer;
    }
}