이 문제 역시 그렇게 어렵지 않았습니다. 문제의 규칙대로 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
를 사용하는 게 좋다고 합니다.
개발
은 예술
이고 서비스
는 작품
이다.