Today I Learned

오늘도 코틀린 코테 연습!

정수 삼각형

백준 1932번 https://www.acmicpc.net/problem/1932

문제

위 그림은 크기가 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를 사용하여 각 위치까지의 최대 합을 계산해 풀었다.

1. 정수 삼각형의 높이를 받고, 각 줄마다의 정수들을 2차원 배열로 저장한다.

2. DP로 이용할 2차원 배열을 초기화한다. 여기서 각 위치까지의 최대 합을 저장한다. 첫번째 줄은 입력으로 들어온 첫번째 줄과 동일하게 초기화한다.

3. 2중 for문을 이용과 dp를 이용해 각 위치까지의 최대 합을 계산한다. 이전 줄의 값과 현재 줄의 값을 더하여 현재 위치까지의 최대 합을 계산하고 갱신한다.

4. 마지막으로 계산된 최대 합 중 가장 큰 값을 출력하면 완료!

Kotlin 코드

fun main() {
    val n = readln().toInt()

    val triangle = Array(n) { readln().split(" ").map { it.toInt() }.toIntArray() }

    val dp = Array(n) { IntArray(it + 1) }

    dp[0][0] = triangle[0][0]

    for (i in 1 until n) {
        for (j in 0..i) {
            dp[i][j] = triangle[i][j] + maxOf(getValue(dp, i - 1, j - 1), getValue(dp, i - 1, j))
        }
    }

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

fun getValue(dp: Array<IntArray>, row: Int, col: Int): Int {
    return if (row < 0 || col < 0 || col >= dp[row].size) 0 else dp[row][col]
}