[BOJ 골드5] 배열 탈출

문제

https://www.acmicpc.net/problem/11909

풀이

• 흔한 DP문제여서 시간 거의안들이고 바로 풀렸음

import java.lang.Math.*


fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val map = Array(n){
        List(n){0}
    }
    for(i in 0 until n){
        map[i] = readLine().split(" ").map{it.toInt()}
    }
    val dp = Array(n){
        MutableList(n){0}
    }
    dp[0][0] = 0
    for(i in 1..n-1){
        dp[0][i] = dp[0][i-1]
        dp[i][0] = dp[i-1][0]
        if(map[0][i-1]<=map[0][i]){
            dp[0][i] += (map[0][i]-map[0][i-1]+1)
        }
        if(map[i-1][0]<=map[i][0]){
            dp[i][0] += (map[i][0]-map[i-1][0]+1)
        }
    }

    for(i in 1 until n){
        for(j in 1 until n){
            val down = if(map[i-1][j] <= map[i][j]){
                dp[i-1][j] + (map[i][j]-map[i-1][j]+1)
            }
            else{
                dp[i-1][j]
            }
            val right = if(map[i][j-1] <= map[i][j]){
                dp[i][j-1] + (map[i][j]-map[i][j-1]+1)
            }
            else{
                dp[i][j-1]
            }
            dp[i][j] = min(down,right)
        }
    }
    println(dp[n-1][n-1])
}