Programmers 멀리 뛰기

 

- 목차

 

소개.

"프로그래머스 멀리 뛰기" 문제의 웹 링크를 첨부합니다.

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

프로그래머스

 

 

 

문제 분석.

멀리 뛰기 문제는 대표적인 점화식과 관련된 문제입니다.

제가 시도한 문제 해결의 접근 방법을 나열해보겠습니다.

 

효진이가 1칸을 뛰는 방법.

1칸만큼 점프를 할 수 있으므로 1개의 방법이 존재합니다.

j(1) = 1

 

효진이가 2칸을 뛰는 방법.

1 칸만큼 2 번 점프를 할 수 있고,  2 칸만큼 1 번 점프할 수 있습니다.

j(2) = 2

 

효진이가 3칸을 뛰는 방법.

1 칸만큼 3 번 점프를 할 수 있고, 

2 칸만큼 1 번 점프 & 1 칸만큼 1번 점프할 수 있습니다.

j(3) = 3

 

 

효진이가 4칸을 뛰는 방법.

1 칸만큼 4 번 점프를 할 수 있고, 

2 칸만큼 1 번 점프 & 1 칸만큼 2번 점프할 수 있고,

2 칸만큼 2 번 점프할 수 있고,

j(4) = 5

 

 

이를 점화식의 관점에서 보면,

j(n) = j(n - 1) + j(n - 2) 로 표현할 수 있습니다.

왜냐하면 n - 1 칸을 이동한 후에 1 칸을 이동하는 방법의 수와 n - 2 칸을 이동한 후에 2 칸을 이동하는 경우의 수를 찾으면 되기 때문입니다.

 

 

문제 풀이.

 

< 점화식을 재귀함수로 구현 >

재귀함수로 구현하는 경우에 시간초과가 발생하게 됩니다.

class Solution {
    public long solution(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2; 
        long n_1 = solution(n - 1) % 1234567;
        long n_2 = solution(n - 2) % 1234567;
        return (n_1 + n_2) % 1234567;
    }
}

 

 

 

< 점화식을 합배열로 구현 >

합배열을 통해서 알고리즘을 구현하게 되면 문제가 해결됩니다.

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