프로그래머스 멀리 뛰기 (JAVA)

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

코딩테스트 연습 - 멀리 뛰기

 

저는 해당 문제를 dp를 이용하여 문제를 해결하였습니다.

저는 DP를 통해 해당 위치까지 가는데 몇개의 경로가 있는지 저장하였습니다.

 

import java.util.*;
class Solution {
    private static final int LIMIT = 1234567;
    private static final long NOT_VALID = -1L;
    public long solution(int n) {
        long[] dp = new long[n+1];
        Arrays.fill(dp,NOT_VALID);
        long answer = dfs(0,n,dp) ;
        return answer;
    }
    private long dfs(int position, int n,long[] dp){
        if(position == n){
            return 1;
        }
        if(dp[position] != NOT_VALID){
            return dp[position];
        }
        long result = 0;
        for(int i = 1 ; i <= 2 ; i++){
            if(position + i <= n){
                result += dfs(position + i,n,dp);
                result %= LIMIT;
            }
        }
        dp[position] = result;
        return result;
    }
}