[JAVA][Programmers] 멀리 뛰기 ⭐️

프로그래머스

---

📌 접근 방법

피보나치 수열을 이용하여 풀었습니당.

n	방법	수
1	1	1
2	11 2	2
3	111 12 21	3
4	1111 112 121 211 22	5
5	11111 1112 1121 1211 2111 122 212 221	8

이렇게 규칙을 따라가보면 피보나치 수열로 증가하는 규칙을 찾을 수 있습니다 ! 

---

PASS CODE

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