[프로그래머스] 멀리 뛰기 (Java/자바) - dp

문제

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

프로그래머스

 

풀이

효진이는 1칸 또는 2칸을 뛰어서 이동할 수 있다.

효진이가 3번째 칸에 가려고 하는 경우의 수는

1번째 칸에서 2칸 뛰는 방법 1가지

2번째 칸에서 1칸 뛰는 방법 1가지

따라서, 3번째 칸까지는 1번째 칸까지 가는 방법의 수 + 2번째 칸까지 가는 방법의 수의 값과 같다.

 

다시, 4번째 칸에 가려고 하는 경우의 수는

3번째 칸에서 1칸 뛰는 방법 1가지

2번째 칸에서 2칸 뛰는 방법 1가지

따라서, 4번째 칸까지 가는 방법의 수는 3번째 칸을 가는 방법의 수 + 2번째 칸을 가는 방법의 수

 

주의

이유는 못 찾았는데... dp배열 선언 시, n+1 사이즈로 선언하면 메모리 때문인지 정답 테케 1번이 안 맞는다..

그래서 최대 사이즈 + 1인 2001로 선언

 

전체 코드

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