[프로그래머스] 멀리 뛰기 - 자바(Java)

문제 링크

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

프로그래머스

 

 

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한 번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는

(1칸, 1칸, 1칸, 1칸)

(1칸, 2칸, 1칸)

(1칸, 1칸, 2칸)

(2칸, 1칸, 1칸)

(2칸, 2칸)

의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567을 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

 

 

제한사항

• n은 1 이상, 2000 이하인 정수입니다.

 

 

입출력 예

n	result
4	5
3	3

 

 

입출력 예 설명

입출력 예 #1

위에서 설명한 내용과 같습니다.

 

입출력 예 #2

(2칸, 1칸)(1칸, 2칸)(1칸, 1칸, 1칸)총 3가지 방법으로 멀리 뛸 수 있습니다.

 

 

코드

class Solution {
    public long solution(int n) {
        // 길이가 2001인 dp 배열 선언
        int[] dp = new int[2001];
        dp[1] = 1; // n이 1일 때 방법의 수
        dp[2] = 2; // n이 2일 때 방법의 수

        // i = 3부터 dp 길이까지 반복
        for (int i = 3; i < dp.length; i++) {
            // i - 2일 때 방법의 수 + i - 1일 때 방법의 수를 저장
            dp[i] = (dp[i - 2] + dp[i - 1]) % 1234567;
        }

        return dp[n];
    }
}

코드 설명

주석 참고

• 이 문제는 멀리뛰기하는 방법의 수를 계산하는 문제다. 다이나믹 프로그래밍(DP)을 활용하여 시작점에서 주어진 n까지 멀리뛰기를 하는 방법의 수를 찾을 수 있다.
• n은 2000 이하이기 때문에 배열의 크기가 2001인 dp 배열을 초기화한다.
• dp[1]과 dp[2]에 n이 1일 때와 2일 때 멀리뛰기를 하는 방법의 수를 초기화한다. (1일 때는 1, 2일 때는 2가지 방법으로 멀리 뛰기를 할 수 있다.)
• for 문을 통해 i가 3부터 dp 배열의 길이까지 반복하여 (dp[i - 2] + dp[i - 1]) 합하여 dp[i]에 저장한다.
• 문제에서 1234567을 나눈 나머지를 리턴하라는 요구가 있으므로 위 연산에 % 1234567을 계산한다.
• 반복문을 마친 후 dp[n]을 반환한다. (dp[n]에 n까지 멀리뛰기를 하는 방법의 수가 저장된다.)