[12914] 멀리 뛰기

✔ 멀리 뛰기

[프로그래머스 12914]

문제 분석하기

DP를 사용해 n번째 칸까지 이동한 횟수를 

손으로 풀어보기

1. 점화식의 형태와 의미를 도출
   1. D[i]는 i번째 칸에 도달할 수 있는 경우의 수
2. 점화식을 구함
   1. D[0]은 0
   2. D[1]은 1칸 뛰는 것으로만 가능하므로 1
   3. D[2]는 1칸을 2번, 2칸을 1번 뛰는 것으로 가능하므로 2
   4. 다음 칸으로 1칸 뛸 때 D[i - 1]
   5. 다음 칸으로 2칸 뛸 때 D[i - 2]
3. 점화식으로 D 배열을 채운 후 D[N]을 반환

슈도코드 작성하기

n(멀리뛰기에 사용될 칸의 수)
D(i번째 칸에 도달할 수 있는 경우의 수)
D[1] = 1
D[2] = 2
for(i -> 2000까지) {
    D[i] = (D[i - 1] + D[i - 2]) % 1234567
}
D[n] 반환

코드 구현하기

/**
 * 12914) 멀리_뛰기
 */
public class L011_12914 {
    // n(멀리뛰기에 사용될 칸의 수)
    public long solution(int n) {
        // D(i번째 칸에 도달할 수 있는 경우의 수)
        int[] D = new int[2001];
        D[1] = 1;
        D[2] = 2;
        for (int i = 3; i < 2001; i++) {
            // (이전 칸에서 1칸 뛸 때 + 이전 칸에서 2칸 뛸 때의 경우의 수) % 1234567
            D[i] = (D[i - 1] + D[i - 2]) % 1234567;
        }
        // D[n] 반환
        return D[n];
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L011_12914 solution = new L011_12914();

        int n = 4;

        long result = solution.solution(n);

        System.out.println(result);
    }
}