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

문제

문제 해결

처음에는 같은 것이 있는 순열로 접근하였으나 시간초과가 발생했다..
질문하기 페이지에서 피보나치 수열로 접근하라는 힌트를 얻었다.

n개의 칸에 도달하는 방법의 수 == n-1개의 칸에 도달하는 방법의 수 + n-2개의 칸에 도달하는 방법의 수의 합
n칸에 도달하기까지 방법수는 마지막을 1칸뛰는 방법과 2칸 뛰는 방법을 더한 값이다.

점화식으로 표현

• f(n) = f(n-1) + f(n-2)
• f(1)=1
• f(0)=1

• 동적 계획법을 사용하여 피보나치 수열을 계산한다.
• 오버플로우 방지를 위해 계산된 f(n) 값은 1234567로 나눈 나머지로 저장한다.

코드

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