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

[프로그래머스] level3 멀리뛰기

소요시간 : 7분

 

종이에 적으니까 규칙이 보이길래 코드 짜봤더니 통과 되었다. 

n번째 칸은 n-1번째와 n-2번째 칸의 경우를 더하면 나왔기 때문.

왜냐면 한 칸과 두 칸, 움직이는 경우가 2가지니까!

 

처음엔 문제만 보고 뭔가 dp 문제 아닐까 했는데 풀고나서

다른 사람들 풀이를 보니 dp 풀이도 있고 피보나치 풀이도 있고 다양하구만

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

    long[] arr = new long[n+1];
    arr[1] = 1;
    arr[2] = 2;
    for (int i = 3; i < arr.length; i++) {
    	arr[i] = ((arr[i-2] % 1234567) + (arr[i-1] % 1234567)) % 1234567;
    }
    return arr[n] % 1234567;
  }
}