백준 11060 점프 점프 Kotlin (dp)

문제 출처 : https://www.acmicpc.net/problem/11060

11060번: 점프 점프

문제

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.

출력

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

간단한 dp 문제이다.

i번째 칸에 도착하는 최소 점프 횟수는 몇일까?

0부터 i-1칸에서 i번째 칸으로 점프하는 경우의 수 중에 가장 작은 경우의 수이다.

그럼 j > i라고 할 때  j칸에 도착하는 경우의 수는?

마찬가지로 0부터 j-1칸에서 j번째 칸으로 점프하는 경우의 수 중에 가장 작은 경우의 수이다.

알겠는데, 그럼 그 앞 칸들에서 가장 작은 경우의 수를 가지고 있어야 하지 않나? 이걸 어떻게 구해?

dp[i] = i칸에 도착하는 데에 최소 점프 횟수

만약 dp[3] = 2이고, A[3] = 2이라고 하자. 3번째 칸에선 4,5번째 칸으로 갈 수 있는데, 3번째 칸 까지 도달하는 데에 최소 점프 횟수가 2번이다. 여기서 한 번 더 점프하여 5로 갔다고 칠 때 dp[5] = 3이 되어, 적어도 3번째 칸을 통해 5번째 칸으로 가는 루트에서는 최소한의 점프로 도달했음을 의미한다.

그런데 만약 dp[4]= 1이고 A[4] = 1이면 5번째 칸에 2번 만에 도착할 수 있으므로 dp[5] = min(dp[5], dp[4]+1) = 2가 된다.

즉 점화식은 다음과 같다.

i = 현재 칸

j = 현재 칸에서 갈 수 있는 범위

dp[i+j] = min(dp[i+j], dp[i]+1)

출력은 dp[n-1]이 초기값과 같다면 도달할 수 없다는 의미로 -1을 출력하고 아니라면 dp[n-1]을 출력하자.

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

const val INF = 987654321
fun main() = with(System.out.bufferedWriter()) {
    //input
    val n = getInt()
    val list = getIntList()

    //solve
    val dp = IntArray(n) { INF }
    dp[0] = 0
    for (i in 0 until n - 1) {
        val ai = list[i]
        for(j in i .. i+ai){
            if(j >=n) break
            dp[j] = dp[j].coerceAtMost(dp[i]+1)
        }
    }
    //output
    write("${if(dp[n-1] == INF) -1 else dp[n-1]}")

    close()
}