[BOJ] 이동하기 in Python & Kotlin

문제풀러 가기!

이 문제 역시 그렇게 어렵지 않았습니다. 문제의 규칙대로 2차원 배열의 최대값을 갱신하면 바로 풀리는 문제였습니다. 따라서 2차원 배열을 dp라 했을 때 dp[i][j]의 값은 다음과 같습니다.

dp[i][j] += dp[i-1][j] + dp[i][j-1]

아래는 Python 풀이입니다.

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
zero_arr = [0 for _ in range(m+1)]

arr = [zero_arr]
for _ in range(n):
    arr.append([0] + list(map(int, input().split())))

for i in range(1, n+1):
    for j in range(1, m+1):
        arr[i][j] += max(arr[i-1][j], arr[i][j-1])

print(arr[n][m])

아래는 Kotlin 풀이입니다.

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val ex = br.readLine().split(" ").map { it.toInt() }
    val n = ex[0] + 1
    val m = ex[1] + 1

    val dp = Array(n){ IntArray(m){0} }

    for (i in 1 until n) {
        var candy = br.readLine().split(" ").map { it.toInt() }
        for (j in 1 until m) {
            dp[i][j] = candy[j-1]
        }
    }

    for (i in 1 until n) {
        for (j in 1 until m) {
            dp[i][j] += maxOf(dp[i-1][j], dp[i][j-1])
        }
    }
    println(dp[n-1][m-1])
}

주의할 점은 많은 수의 행을 입력받는 것은 입력에 많은 시간이 걸릴 수 있으니

sys.stdin.readline 이나 BufferedReader를 사용하는 게 좋다고 합니다.

개발은 예술이고 서비스는 작품이다.