[Python/Kotlin] 백준 1932번 : 정수 삼각형

백준 문제 주소 https://www.acmicpc.net/problem/1932

문제

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

30

---

요즘 dp 문제를 계속 풀었더니 슬슬 어떻게 풀어야되는지 익숙해지는 중인 것 같다.
이 문제의 핵심은 아래와 같다.
dp[i][j] = arr[i][j] + max(dp[i-1][j], dp[i-1][j-1])
그 경로의 최댓값을 저장하는 방식이다.
그 칸의 값과 그 칸 전의 값 두 개를 비교하여 더 큰 값을 더해서 결과적으로 그 루트의 가장 큰 값을 만드는 것이다.

Python 풀이

n = int(input())
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))

for i in range(1,n):
    for j in range(i+1):
        if j == 0:
            arr[i][j] = arr[i][j] + arr[i-1][j]
        elif i == j:
            arr[i][j] = arr[i][j] + arr[i-1][j-1]
        else:
            arr[i][j] = arr[i][j] + max(arr[i-1][j], arr[i-1][j-1])
print(max(arr[n-1]))

Kotlin 풀이

import java.io.*
import java.util.*

fun main(args: Array<String>)
{
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val arr = Array(n){Array(n){0}}

    for (i in 0 until n) {
        val st = StringTokenizer(br.readLine())
        for(j in 0..i) {
            arr[i][j] = st.nextToken().toInt()
        }
    }

    for (i in 1 until n) {
        for(j in 0..i) {
            when(j) {
                0 -> arr[i][j] = arr[i][j] + arr[i-1][j]
                i -> arr[i][j] = arr[i][j] + arr[i-1][j-1]
                else -> arr[i][j] = arr[i][j] + Math.max(arr[i-1][j], arr[i-1][j-1])
            }
        }
    }

    println(arr[n-1].maxOrNull())
}