문제

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

나의 풀이

• 우연히 아무거나 찍었는데 어제와 비슷한 피보나치 수 관련 문제라서 쉽게 해결할 수 있었다.

class Solution {
    public long solution(int n) {
        long answer = 0;
        List<Integer> list = new ArrayList<>();

        list.add(0);
        list.add(1);
        list.add(2);

        for (int i = 3; i < n+1; i++) {
            list.add(list.get(i-2) % 1234567 + list.get(i-1) % 1234567);
        }

        answer = list.get(n) % 1234567;

        return answer;
    }
}

피보나치 수

1칸까지 뛰는 방법은 1가지, 2칸까지 뛰는 방법이 2가지인 것은 쉽게 알 수 있다.
이제 n칸까지 뛰는 방법은 다음과 같이 생각해 보자.

- [n - 1]번째 칸에서 1칸을 뛰어서 n번째 칸에 도착
- [n - 2]번째 칸에서 2칸을 뛰어서 n번째 칸에 도착

첫 번째 방법은 마지막에 1칸을 뛰어서 도착했고, 
두 번째 방법은 마지막에 2칸을 뛰어서 도착했기 때문에, 위 두가지 방법 중 서로 중복되는 경우는 없다.
따라서 n번째 칸으로 뛰는 방법의 수는 
[n-1]번째 칸으로 뛰는 방법 수 + [n-2]번째 칸으로 뛰는 방법의 수가 됨 
  -> 피보나치 수열과 동일