멀리 뛰기

문제

주어지는 n 칸 만큼 뛰어서 가는 경우의 수를 구하는 문제.
주인공 효진이는 1칸 또는 2칸씩 뛰어갈 수 있다.

풀이

첫번째 풀이방법 DFS 이용

class Solution {

    static int answer=0;
    
    public static void DFS(int cnt, int n){
        if(cnt==n){
            answer++;
            return;
        }
        if(cnt>n) return;
        else{
                DFS(cnt+1,n);
                DFS(cnt+2,n);
            }
    }

    public long solution(int n) {
        DFS(0,n);
        return answer%1234567;
    }
}

처음엔 그냥 DFS에 익숙해서 DFS로 시도했다. 근데 n의 값이 2000까지 입력될수있기에 런타임에러가 발생한다. 그래서 DFS 상위호환인 DP방식으로 문제를 풀어야겠다고 생각했다.

두번쨰 풀이방법 DP 이용

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

DP를 이용해서 문제를 풀기위해서는 점화식을 찾아야한다. n이 1,2 일 경우의 경우의 수를 배열 ch에 저장해둔다. 그러고 3,4,5,6 에서의 경우의 수를 계산해서 점화식을 찾는다. 그것을 for문을 이용해 ch배열에 저장해둔다. 끝.