[알고리즘] 프로그래머스 - 멀리뛰기 Java Lv02

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

프로그래머스

 

package Programmers;
public class 멀리뛰기 {

    public static void main(String[] args){
        멀리뛰기 T= new 멀리뛰기();
        int n = 4;
        T.solution(n);
    }
    public long solution(int n) {
        long[] arr = new long[n + 2];

        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 2;

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

        return arr[n];
    }


}

1. 풀이

 - DP로 풀어야한다. DFS, BFS는 시간초과나옴

 - n 값이 0 일때는 답이 0 개 

    1 일때는 1개

    2 일때는 2개

    3 일때는 3개

    4 일때는 5개 

    5 일때는 8개 

    ........ 

   규칙이 나오는데 피보나치 수열이다 arr[i-1] + arr[i-2] = arr[i] 

   2번째 배열까지는 값을 직접 박아주고 이후부터 arr에 값을 구하면된다. 

   구하고자하는답은 1234567을 나눈 나머지를 구하라고 하니까 arr에 넣고 마지막에 그냥 리턴해준다.