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

코딩테스트 연습 - 멀리뛰기

프로그래머스

문제 설명

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

 

시도

fun solution(n: Int): Long {
    val dp = LongArray(n + 1) { 1 } // dp[0] = 1 // dp[1] = 1

    // DP(Dynamic Programming)
    for (i in 2..n) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567
    }
    return dp[n]
}

성능요약:  메모리: 61.3 MB, 시간: 0.14 ms

 

접근

문제 접근

이 문제는 피보나치수열과 동일한 구조를 가지고 있다. 피보나치수열에서 각 항은 그전 두항의 합으로 계산된다. 이는 효진이가 한 번에 1칸 또는 2칸을 뛸 수 있는 동작에 따른 것이다.

 

효진이가 n번째 칸에 도달하려면, 그 전의 위치는 n-1번째 칸 또는 n-2번째 칸일 수밖에 없다.

• 만약 n-1번째 칸에서 왔다면, 1칸을 뛰었을 것이고,
• 만약 n-2번째 칸에서 왔다면, 2칸을 뛰었을 것이다.

따라서, 효진이가 n번째 칸에 도달하는 방법의 수는 "n-1번째 칸에 도달하는 방법의 수" + "n-2번째 칸에 도달하는 방법의 수"로 계산된다.

 

이런 식으로, 매번 각 칸에 도달할 수 있는 방법의 수를 구하고 이를 저장하면, 이후에 이 정보를 바탕으로 다음 칸에 도달할 수 있는 방법의 수를 더 빠르게 계산할 수 있다. 이러한 방식으로 문제를 접근하는 방법을 동적 프로그래밍(Dynamic Programming, DP)라고 부른다.

 

풀이

1. `dp` 배열을 선언하고, 모든 요소를 1로 초기화한다. `dp` 배열의 `i`번째 요소는 `i`칸을 뛸 수 있는 방법의 수를 저장한다. (효진이가 0 또는 1칸을 뛸 수 있는 방법은 오직 한 가지밖에 없기 때문에 `dp[0]` = 1, `dp[1]` = 1)
2. `i`가 2부터 `n`까지 순회하면서, 각 `i`에 대해 `dp[i]`는 `dp[i-1]`(즉, `i-1`칸에서 한 칸 뛰는 경우)와 `dp[i-2]`(즉, `i-2`칸에서 두 칸 뛰는 경우)를 합한 것이다. 이 값을 1234567로 나눈 나머지를 `dp[i]`에 저장한다.

 

 

 

언제나 잘못된 설명이나 부족한 부분에 대한 피드백은 환영입니다🤍