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

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

프로그래머스

---

 

문제

 

풀이

계단을 올라갈 수 있는 방법은 1칸 혹은 2칸을 올라가는 방법입니다. 그렇다면 i번째 계단을 올라올 수 있는 방법은 i-1번째 계단에서 1칸 올라오는 방법, i-2번째 계단에서 2칸 올라오는 방법, 총 2가지 경우일 것입니다.

따라서 점화식은 dp[i] = dp[i-1] + dp[i-2] 라고 쓸 수 있습니다.

 

이 때 dp[0]은 0번째 계단이기 때문에 0이 되고, dp[1]은 1칸 올라가는 방법 1개이므로 1이 되고, dp[2]는 1칸, 1칸 올라가는 방법, 2칸 올라가는 방법 2가지이므로 2가 됩니다.

 

⚠주의해야할 부분⚠이 여기서 나오는 데 최소 dp[0], dp[1], dp[2] 3개는 만들어야 하므로 dp 배열을 선언할 때 n + 2개로 선언해야합니다! 만약 dp 배열을 n+1개로 선언하고, n이 1이라면 배열의 크기가 2 이므로, dp[2] = 2에서 오류가 생깁니다!

 

문제에서 방법의 가지 수에 1234567를 나눈 나머지를 리턴하라고 했으므로 각 dp 값마다 1234567로 나눈 나머지를 넣어주면 됩니다. 모듈러 연산의 덧셈 법칙으로 인해 계산이 가능합니다!

 

 

소스코드

import java.util.*;

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

 

---

마치며 ...

처음에 dp 크기를 n+1로 했다가 테스트 1번에서만 런타임 오류가 났다. 왜일까.. 생각해봤는데 dp[2]를 넣어줬기 때문이었다..! 이전에 풀었던 프로그래머스 아이템 줍기에서도 같은 이유로 배열의 크기를 1개 늘려줬었는데 왜 그런지 확실히 알았다. 배열을 선언하고 값을 바로 넣어줄 때는 꼭 배열의 크기를 고려해서 설정해주자!