<프로그래머스> 멀리 뛰기(Lv.2)

https://github.com/heesoo-park/ForCodeKata/tree/main/%EB%A9%80%EB%A6%AC%20%EB%9B%B0%EA%B8%B0

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

 

이 문제는 보자마자 바로 '아...! 그 문제다' 싶었다.

코틀린으로는 프로그래머스 문제, 자바로는 백준 문제를 풀고 있는데 최근에 백준에서 봤던 유형같았기 때문이다.

역시 코딩 문제들은 많이 풀면 풀수록 그 유형이겠거니 하는 느낌이 오게 되는 것 같다.

 

---

'전에 이 유형 풀 때 DP를 사용해서 했으니까 여기에도 적용시켜서 해보면 될 거 같고... 1칸부터 써보면서 규칙을 찾아보자!'

 

---

 

찾아낸 규칙은 dp[i] = dp[i - 1] + dp[i - 2] 였다.

아주 기쁘게 코드를 다 작성하고 제출했는데...

첫번째 케이스에서 런타임 에러가 떴다.

'어이가 없네...?' 하며 이유를 찾아보니까 납득이 가고 이 부분에 대해서는 매번 놓친다는 걸 알았다.

바로 배열을 동적할당하여 문제를 풀 때 크기 너머의 인덱스를 접근하는 경우다.

배열의 크기는 2인데 배열 인덱스 2에 접근하는 경우...

 

그래서 수정을 아주 깔끔하게 했다.

그냥 제한 사항의 최대 숫자로 했다..ㅎㅎ

이 방법이 아니면 조건문으로 입력값에 따라 기본적으로 초기화하는 인덱스 접근을 제한하는 식으로 해도 된다.

 

해당 방법으로 작성한 코드는 다음과 같다.

class Solution {
    fun solution(n: Int): Long {
        val dp = LongArray(2001)

        dp[1] = 1
        dp[2] = 2
        
        for (i in 3..n) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567
        }

        return dp[n]
    }
}