[Java][Programmers]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 이하인 정수입니다.

 

문제를 보고 3가지의 접근 방법으로 생각해보았다.

 

1. 중복순열?
n칸을 이동할 때, 모두 1칸씩 이동한다면 총 n번의 점프가 있을거고

Size = n 의 순열 각 자리에 1 또는 2 를 넣어가며 반복 -> 각 자리의 값의 합이 n이 되었을 때

카운트를 증가시키면 되지 않을까? 

 

2. DFS?

1칸 뛰기를 선택하는 경우, 2칸뛰기를 선택하는 경우로 나뉘어 재귀함수를 수행하고,

전체 점프 칸의 합이 n이 되면 카운트하는 방법으로 가능하지 않을까?

 

3. DP (선택!)

위 문제의 규칙성을 찾아보면

f(1) = 1 --- (1)

f(2) = 2 --- (1, 1) (2)

f(3) = 3 --- (1, 2) (1, 1, 1)  (2, 1)

f(4) = 5 --- (1, 1, 2) (2, 2) (1, 2, 1) (1, 1, 1, 1) (2, 1, 1)

...

다음과 같이 되는것을 볼 수 있다. 그림으로 살펴보면 이렇다. 

마지막 칸부터 생각해보면 n번째 칸에 도달하는 경우는 두가지로 분류된다.

n-2번째 칸에서 2칸을 이동하는 경우와 n-1번째 칸에서 1칸을 이동하는 경우.

즉, n번째 칸에 도착하는 경우의 수는

n-2번째 칸에 도착하는 경우의 수와 n-1번째 칸에 도착하는 경우의 수의 합과 같다.

이를 통해 점화식을 세우면 f(n) = f(n-2) + f(n-1) 이 만들어진다. 

 

소스코드

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

 

사실 나는 이전에 비슷한 유형의 문제를 풀어봤기때문에 DP로 접근을 할 수 있었지만,

처음에 이 방법을 생각해 내는 것은 쉽지 않은듯 하다 ㅠ

 

하지만 이것만 생각해낸다면 아주 쉽게 풀 수 있기에..

역시 연습이 답이다..

 

---

programmers.co.kr/learn/courses/30/lessons/12914

코딩테스트 연습 - 멀리 뛰기