문제

정답 코드

class Solution {
    public long solution(int n) {
        long answer = 0;
        if (n==1) return 1;
        if (n==2) return 2;

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

        longs[1]=1;
        longs[2]=2;

        for (int i=3;i< longs.length;i++) {
            longs[i]=(longs[i-1]+longs[i-2])%1234567;
        }

        answer=longs[n];

        return answer;
    }
}

숫자를 나열해보니 피보나치수열이었다..!!
피보나치는 얼마전에 풀었던 문제이기 때문에 쉽게 답이 나왔다.

그러나 이게 피보나치라는걸 발견하지 못했다면..? 어떻게 풀었을까?

다른 사람들도 피보나치 수열을 이용해서 풀었다.