[JAVA/코딩테스트] 멀리 뛰기

문제

 

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

프로그래머스

 

문제힌트

 

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

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

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

 

 

해결

class Solution {
  public long solution(int n) {
        long answer = 1;

        long a = 0;
        long b = 1;

        for(int i=0; i<n; i++){
            long z = b;
            b = (a+b) % 1234567;
            a = z;
        }
        answer = b;
        return answer;
    }
}