[백준][KOTLIN] 1932 정수 삼각형

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

1932번: 정수 삼각형

풀이

• 위의 과정에 나온 규칙성을 이용하여 동적프로그래밍으로 해결한다.

코드

import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val input = Array(n + 1) { IntArray(n + 1)}
    val dp = Array(n + 1) { IntArray(n + 1) }

    for (i in 1..n) {
        for (j in 1..i) {
            input[i][j] = sc.nextInt()
            dp[i][j] = input[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j])
        }
    }

    var result = dp[1][1]

    for (i in 2..n) {
        if (result < dp[n][i]) {
            result = dp[n][i]
        }
    }

    println("$result")
}

private fun max(a: Int, b: Int): Int {
    return if (a < b) b else a
}