[프로그래머스][Java] Lv.2 멀리 뛰기

---

Thinking

n에 도착하는 방법은 (n-1에서 1칸 뛰어서 오는 방법)과  (n-2에서 2칸 뛰어서 오는 방법)을 합치는 것입니다.

따라서 dp를 사용할 때 문제를 더 쉽게 풀 수 있습니다.

풀이과정

1. cnt배열을 사용해 n까지의 dp 과정을 저장합니다.
2. 1칸에 도착하는 방법은 0에서 1로 한 칸 뛰는 방법 밖에 없으므로 cnt[1]=1입니다.
3. 2칸에 도착하는 방법은 0에서 2로 한 번에 뛰는 방법과 1에서 1칸 뛰는 방법 총 2입니다.
4. 1과 2 값을 초기화한 이후에 3부터 n에 도달할 때까지 dp를 돌면서 n에 도달하는 방법 수를 구합니다.
   (* 주의해야 할 부분은 dp를 하면서 매번 1234567로 나눈 나머지를 return 하는 것입니다.)

---

전체 코드

class Solution {
    static int mod=1234567;
    static long cnt[];
    public long solution(int n) {
        long answer = 0;
        
        
        // cnt[2]까지 값을 넣어주기 때문에
        //long[n+1]로 초기화를 해주면 인덱스 초과 에러가 난다.
        cnt = new long[n+2]; //  n+1로 하면 런타임 에러.
        cnt[1]=1;
        cnt[2]=2; 
        
        for(int i=3;i<=n;i++){
            dp(i);
        }
        
        return cnt[n];
    }
    // 동적계획법
    void dp(int n){
        
        cnt[n]= (cnt[n-1]%mod + cnt[n-2]%mod) %mod;
    }
}