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

📌 문제

멀리뛰기 - Lv2

프로그래머스

 

📌 풀이

• 맨 처음에는 2를 나눠서 개수를 늘리는 방식을 생각했습니다... ➡️ 매우 큰 삽질...
• ❗️그러나 이 문제의 힌트는 멀리뛰기 할 수 있는  칸의 수가 1 또는 2 라는 곳에 있습니다.
• 멀리뛰기 할 수 있는 칸 수가 정해져 있으므로
• 총 점프한 거리는 점프하고자 하는 위치에서 1칸 전인 곳과 2칸 전인 곳에서 점프하는 경우로 생각할 수 있습니다..
• 따라서  numList[i] = numList[i-1] + numList[i-2] 다음과 같은 점화식이 성립합니다.

 

📌 코드

class Solution {
    public long solution(int n) {
        long answer = 0;

        long[] numList = new long[n + 1];
        

        //초기값 세팅
        numList[0] = 1;
        numList[1] = 1;
        
        for(int i = 2; i <= n; i++){
            numList[i] = (numList[i-1] + numList[i-2]) % 1234567;
        }
        return numList[n];
        
    }
}