[백준/코틀린] 1932번: 정수 삼각형

링크

1932번: 정수 삼각형

풀이

dp[i][j]: 맨 위에서부터 i번째 줄의 j번째 값까지 내려올 때 만들 수 있는 최대 누적 합

정수 삼각형의 (i, j) 위치에 도달하는 경로는 다음 두 가지입니다.

• 왼쪽 위에서 내려오는 경로 → dp[i-1][j-1]
• 오른쪽 위에서 내려오는 경로 → dp[i-1][j]

따라서 두 경로 중 큰 값을 선택하고 현재 값을 더해 dp[i][j]를 계산합니다.

코드

fun main() {
    val n = readln().toInt()
    val dp = List(n + 1) { MutableList(n + 1) { 0 } }

    for (i in 1..n) {
        val row = readln().split(" ").map { it.toInt() }

        for (j in 1..i) {
            dp[i][j] = row[j - 1] + maxOf(dp[i - 1][j - 1], dp[i - 1][j])
        }
    }

    println(dp[n].maxOrNull())
}