멀리 뛰기

문제 링크

문제 요약

• 한 칸 또는 두 칸씩 뛰어 n칸 끝에 도달하는 방법의 수를 구한다
• 답은 1234567로 나눈 나머지를 반환한다
• n은 최대 2000

문제 풀이

처음에는 재귀로 모든 경우를 직접 세어보면 될 줄 알았다.

매 칸에서 1칸을 뛰는 경우와 2칸을 뛰는 경우로 나눠 재귀 호출을 두 번씩 하는 방식이다.

하지만 이 방식은 n이 커지면 감당할 수 없다.

매 칸마다 경우의 수가 두 갈래로 나뉘기 때문에 호출 횟수가 2^n에 가깝게 늘어난다.

n이 최대 2000까지 주어지므로 이 방식으로는 시간 안에 답을 구할 수 없다.

이 문제의 핵심은 n칸에 도달하는 방법의 수가 n-1칸과 n-2칸에 도달하는 방법의 수의 합이라는 점이다.

마지막 한 걸음을 1칸으로 들어오는 경우와 2칸으로 들어오는 경우로 나누면, 그 직전 상태는 각각 dp[n-1]과 dp[n-2]가 된다.

• dp[1] = 1, dp[2] = 2로 시작한다
• dp[i] = dp[i-1] + dp[i-2]를 1234567로 나눈 나머지로 채운다
• 각 칸을 한 번씩만 계산하면 되므로 n번의 반복만으로 답을 구할 수 있다

최종 코드

class Solution {
    public long solution(int n) {
        if(n==1)
            return 1;
        
        long[] dp = new long[n+1]; // dp[i]: i칸에 도달하는 방법의 수
        
        dp[1] = 1;
        dp[2] = 2; // 1칸, 2칸일 때의 경우의 수는 직접 채운다
        
        for(int i=3;i<=n;i++){
            dp[i] = (dp[i-1] + dp[i-2]) % 1234567; // 마지막 걸음을 1칸, 2칸으로 들어오는 두 경우를 합산
        }
        
        return dp[n];
    }
}