멀리 뛰기

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

 

1 1
2 11 2
3 111 12 21
4 1111 112 121 211 22
5 11111 1112 1121 1211 2111 122 212 221
6 111111 11112 11121 11211 12111 21111 1122 1212 1221 2112 2121 2211 222

 

규칙을 확인한 결과 피보나치 수열을 띄고 있었다.