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

멀리뛰기

문제링크

풀이

dp를 활용해 문제를 풀었다.
경우의 수를 확인하는 데 하다보니 규칙을 찾아서 3일 경우 2의 경우의 수 + 1의 경우의 수라는 점을 알게 되었다.
해당 3의 경우의 수 = 2의 수에 앞에 1더하거나 1의 경우의 앞에 2의 경우수를 더한 것과 같다.

코드

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

        return dp[n] % 1234567L;
    }
    
}