[프로그래머스] 멀리 뛰기 - JAVA

문제

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

프로그래머스

 

풀이

N=1부터 나올 수 있는 개수를 구해보면 다음과 같다.

N=1 -> 1

N=2 -> 2

N=3 -> 3

N=4 -> 5

N=5 -> 8

 

즉, n=i-1 과 n=i-2일때의 개수를 더하면 n=i 일때의 개수가 나온다

즉, dp를 방법의 가지수라고 한다면 점화식은 dp[i] = dp[i-1]+d[i-2] 가 된다

 

 

코드

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