(Java) 프로그래머스 - 멀리뛰기

레벨 2 치고는 너무 쉬운 문제였다. 이게 왜 레벨 2에 있는지 모를 정도로...

예전에 백준에서 비슷한 문제를 풀어봐서인지 문제를 보자마자 DP로 풀었다.

 

거리가 1일 때는 뛰는 방법이 1칸 이동 -  1가지

거리가 2일 때는 뛰는 방법이 (1칸 이동, 1칸 이동), (2칸 이동) - 2가지

거리가 3일 때는 뛰는 방법이 (1칸 이동, 1칸이동, 1칸 이동), (1칸이동, 2칸이동), (2칸이동 1칸이동) - 3가지

따라서 dp [i] = dp[i-1] + dp[i - 2]이라는 점화식이 바로 나온다.

오버플로우 때문에 dp [i]을 구할 때마다 1234567로 나눈 나머지를 해줘야 한다.

n이 1인 경우 런타임 에러가 나서 따로 빼주었다.

---

최종 코드

class Solution {
    public long solution(int n) {
        long answer = 0;
        
        // n이 1인 경우
        if(n == 1) {
            return 1;
        }
        
        long[] dp = new long[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i < n + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        answer = dp[n];
        return answer;
    }
}