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

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

프로그래머스

---

코드

class Solution {
    public long solution(int n) {
        /*
        가장 최소의 경우
            2로 나누어 떨어짐 O : 모든 칸을 2로 뛴다.
            2로 나누어 떨이짐 X : 한칸 뺴고 2로 뛴다.
        */
        /*
        2222
        22112
        22121
        22211
        221111
        
        2111111
        211112
        211121
        211211
        21122
        212111
        
        211111111
        21111112
        21111121
        21211211
        */
        /*
        질문하기를 통해 보니 '피보나치 수열'이었다..
        */
        long[] dp = new long[n+2];
        dp[0]=0L;
        dp[1]=1L;
        
        
        for(int i=2; i<n+2; i++){
            dp[i]=(dp[i-2]+dp[i-1])%1234567;
        }
        
        return dp[n+1];
    }
}

바로 피보나치가 떠오르진 않았다.

규칙성을 찾기위해 경우의 수를 늘어놓았지만 보이지 않았다.

질문하기를 통해 피보나치 수열임을 알게 되었다.

아래 그림과 같이 피보나치에서 경우의 수에 대한 증명도 있었다.

 

피보나치 경우의 수 증명

 

그리고 오버플로우 문제도 발생했는데 DP 배열에 저장할 때 1234567로 처리한 값을 저장하도록 하여 해결했다.

 

 

문제를 많이 풀어봐야겠다.

시간은 20분 정도 소요되었다.