[Java/자바] 프로그래머스 Lv2 - 멀리 뛰기(DP알고리즘)

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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

---

Solution.java

이 문제는 DP 알고리즘을 활용하여 풀 수 있는 문제입니다.

 

칸이 n개일 때 방법수와 방법 예시를 적은 아래의 표를 간단히 봅시다.

총 칸	방법 수	방법 예시
1	1	(1)
2	2	(1 + 1), (2)
3	3	(1 + 1 + 1), (1 + 2), (2 + 1)
4	5	(1 + 1 + 1 + 1), (1 + 1 + 2), (2 + 2), (2 + 1 + 1), (1 + 2 + 1)

이 표에서 n칸을 뛸 경우의 방법 수는 dp[i] = dp[i - 1] + dp[i - 2] 인 것을 구할 수 있습니다.

 

이 DP 점화식을 적용하여 코드를 풀어봅시다.

 

public class 멀리뛰기 {
    public static void main(String[] args) {
        System.out.println(solution(4));
    }

    public static long solution(int n) {
        long[] answer = new long[2001];
        answer[1] = 1;
        answer[2] = 2;

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

        return answer[n];
    }
}

 

문제 풀이

1. 배열의 크기를 2001로 한 이유는 0부터 시작하기 때문입니다.
2. 이 식을 적용하기 위해선 적어도 두 개의 인덱스 번째의 값은 알아야 하기 때문에 [1] 번째와 [2]번째의 방법수를 넣어줍니다.
3. 1, 2 번째 인덱스의 값은 이미 구했기 때문에 3번째 인덱스부터 반복문을 시작합니다.
4. % 1234567을 한 이유는 문제에서도 요구했지만 n이 2000일 때 Long 타입의 값의 범위를 초과하기 때문에 꼭 나머지 연산을 해줘야합니다.