프로그래머스 Lv. 2 멀리 뛰기 JAVA

링크텍스트

설명

DFS만 사용해서 바로 풀었다가 시간초과 떴다. 그래서 메모이제이션기법을 추가했다.

코드

class Solution {
    static long[] dp;

    public long solution(int n) {
        dp = new long[n + 1];
        return dfs(0, n) % 1234567;
    }
    
    public static long dfs(int num, int n) {
        if (num == n) {
            return 1; 
        }
        if (num > n) {
            return 0;
        }
        
        if (dp[num] != 0) {
            return dp[num];
        }
        
        dp[num] = (dfs(num + 1, n) + dfs(num + 2, n)) % 1234567;
        
        return dp[num];
    }
}

다른 사람의 풀이

링크텍스트