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

 

프로그래머스 멀리 뛰기

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

프로그래머스

 

 

이번 포스팅은 멀리 뛰기 입니다.

 

이 문제를 풀려면 bottom-up 방식의  동적 프로그래밍(Dynamic Programming)을 알면 좋습니다.

 

대표적으로 bottom-up 방식은 피보나치 수열이 있습니다.

 

a1 = 1

a2 = 1

a3 = a1 + a2 = 2

a4 = a2 + a3 = 3

 

n ≥ 3 일 때,

An = An-2 + An-1  이 성립됩니다.

 

이렇게 피보나치 수열을 쓸 줄 알면 됩니다.

 

다만 문제에서 보면 조건이 있는데,

 

1234567을 나눈 나머지를 수열의 n번째 항의 값을 넣어줘야합니다.

 

package farJump;

/*
 * 	https://school.programmers.co.kr/learn/courses/30/lessons/12914
 * 
 *  프로그래머스 멀리 뛰기
 * */

public class FarJump {
	public static void main(String[] args) {
		Solution s = new Solution();
		System.out.println(s.solution(4));
		System.out.println(s.solution(5));
		System.out.println(s.solution(11));
	}
}

class Solution {
    public long solution(int n) {
        if(n <= 3) return (long)n;
        
        long[] arr = new long[n+1];
        for(int i = 0; i < 4; i++) {
            arr[i] = i;
        }
        
        int cnt = 3;
        while(cnt <= n) {
            arr[cnt] = (arr[cnt - 1] + arr[cnt - 2]) %1234567;
            cnt++;
        }
        
        return arr[n];
    }
}

 

위의 소스를 실행시켜보면

 

5
8
144

 

의 결과를 확인할 수 있습니다.