멀리 뛰기

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

프로그래머스

 

처음엔 재귀로 풀었다.

 

그런데 테스트케이스 7번부터 시간 초과가 떴다.

 

생각해보면 n이 2000이하의 정수인 만큼.. 시간 초과가 당연한 듯..

 

long cnt = 0L;
void dfs(int n, int dis) {

    int res = n - dis;
    if (res == 0) {
        cnt++;
    } else if (res < 0) {
        return;
    } else {
        dfs(res, 1);
        dfs(res, 2);
    }

}

 

다른 분들의 풀이를 보니 결국 피보나치 수열의 점화식과 일치한다더라.

 

첫번째칸에 도달하는 방법 = 1칸

두번째칸에 도달하는 방법 = 1칸씩 두번 또는 2칸

세번째칸에 도달하는 방법 = 첫번째칸에서 2칸, 두번째칸에서 1칸, 첫번째칸에서 1칸 이동 후 1칸 이동. 그런데 뒤에 2개는 두번째 칸에 도달하는 방법에서 1칸 이동하는 방법과 일치하므로, 첫번째칸에 도달하는 방법 + 두번째칸에 도달하는 방법 이라고 보면 됨

네번째칸에 도달하는 방법 = 두번째칸에 도달하는 방법 + 세번째칸에 도달하는 방법

...

 

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

 

왜 피보나치를 못 떠올렸을까....