[프로그래머스] 멀리 뛰기 (Java)

 

문제

프로그래머스

 

알고리즘

다이나믹 프로그래밍(DP)

 

풀이

효진이는 1칸 혹은 2칸을 뛸 수 있으므로

4번째 칸에 오는 경우의 수는 3번째 칸에서 1칸을 뛰는 경우의 수 + 2번째 칸에서 2칸을 뛰는 경우의 수일 것이다.

 

즉 i번째 칸에 오는 경우의 수를 dp[i] 라고 하면

dp[i] = dp[i-1] + dp[i-2] 가 된다.

 

 

코드

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