[프로그래머스] 멀리 뛰기

문제

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

문제 출처

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

생각

n	가능한 경우의 수	개수	조합식 표현
1	(1)	1가지	1C0
2	(1,1) (2)	2가지	2C0 + 1C1
3	(1,1,1) (2,1) (1,2)	3가지	3C0 + 2C1
4	(1,1,1,1) (2,1,1,1) (1,2,1,1) (1,1,2,1) (1,1,1,2) (2,2)	5가지	4C0 + 3C1 + 2C2

• 두가지의 방법을 생각했다 이전 두 항의 합이 현재 항과 같기 때문에, DP를 써서 풀 수도 있고, 조합의 누적 합으로 풀 수도 있다
• 1234567로 나눈 나머지를 구하라는 것을 보면, 그리고 combination 계산하다보면 factorial 계산이기에 숫자가 많이 커질 것이라고 생각해 첫 번째 DP를 사용하는 방법을 선택하였다 🤓

코드

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

다른 사람의 풀이

• 대부분의 사람들이 DP를 사용하여 풀었다
• 조합(combination)을 사용한 풀이들도 존재했으니 대부분 문제의 조건이 바뀌기 전에 푼 풀이인 것 같다 돌려보니 시간초과가 발생했다