프로그래머스 12914 멀리 뛰기 자바 풀이

난이도 Lv. 4

풀이일 : 2410244

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

프로그래머스

---

문제

---

아이디어

칸	0	1	2	3	4	5
방법 수	0	1	2	3	5	8

• 3부터는 (n-1) + (n-2) 형태로 방법의 수가 증가한다
• dp로 방법의 수를 더해나가자
• 1234567로 나눈 나머지를 기록하여 숫자가 커지지 않게 조절하자

---

풀이

class Solution {
    public int solution(int n) {
        int answer = 0;
        int[] dp = new int[n+1]; // 1 런타임 에러 방지
        
        for (int i = 0; i < n; i++) {
            // 0, 1 예외처리
            if (i < 2) {
                dp[i] = (i + 1) % 1234567;
            } else {
                dp[i] = (dp[i-1] + dp[i-2]) % 1234567;
            }
        }
        
        answer = dp[n-1];
        return answer;
    }
}

• dp 크기는 n이 1일때의 런타임에러 방지를 위해 n+1로 설정
• 반복문을 순회하며, i가 0, 1일 경우 예외 처리로 dp 기록
• i가 2 이상일 경우, (n-1) + (n-2) 정보를 더해 dp 기록
• 다만 dp 기록 시, 숫자가 커지는 것을 방지하기 위해 처음부터 1234567로 나누어 기록한다.

---

느낀점

• dp 어렵다ㅠ 조금 더 자주 풀고 익숙해지는 시간이 필요할 것 같다.