1932번: 정수 삼각형 - Kotlin

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번째 줄까지 정수 삼각형이 주어진다.

출력

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

 

 

나의 풀이

 이 문제를 풀면서 DP를 어떻게 해결해야 하는지 익숙해지기 시작했다. DP를 풀 때 가장 중요한건 뒤에서 부터 생각하는 것이었다. 

 

 먼저 구하고자 하는 값은 각 층에 숫자를 하나씩 선택했을때의 최대 값을 구하는 것이다. 그렇다면 가장 마지막 줄로 가 보아야 한다.

 주어진 입력은 다음과 같다.

 

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

 

 마지막 줄은 4, 5, 2, 6, 5 이렇게 n의 개수만큼 숫자가 있다. 그 말은 즉슨, 최대 값이 나올 수 있는 가능성은 마지막 숫자가 4, 5, 2, 6 ,5일 때 최대 5가지가 존재한다는 것이다. 이제 이걸 알았으면, 다음은 f(n)을 f(n - 1)이나 f(n - 2)로 구하는 방법을 찾는 것이다.

 

 

      7

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

 

 위의 삼각형을 보게 되면 마지막 숫자로 갈 수 있는 숫자는 2와 7이 존재한다는 것을 알 수 있다. 우리는 이것으로 마지막 숫자가 5인 가능성에서는 2와 7일때의 최대값과 5를 더한 숫자가 최대값이 된다는 것을 알 수 있다. 그럼 이제 다시 입력으로 돌아와보자.

 

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

 

 위의 입력을 2차원 배열로 나타낸다면 5의 위치는 [4][2]가 될 것이다. 2와 7의 위치는 [3][1], [3][2]임으로 우리는 이것으로 부터 다음의 수식을 얻을 수 있다.

 

            dp[i][k] = max(dp[i - 1][k - 1] + 현재 값(5), dp[i - 1][k] + 현재 값(5))

 

 이제 위의 수식을 얻었으니 문제를 해결할 일만 남았다. 그런데 생각해보니 0열일 경우에는 0 -1을 하게 되니 문제가 발생한다. 여기서는 이제 센스가 필요하다. 나는 첫번째 열에 0을 추가하였다. 그리고 남은 공간에도 0을 채워넣었다.

 

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

 

 이 문제는 최대값을 구하는 문제이기에 이렇게 0을 넣어줘도 최대값을 구할 때, 0이 들어간 공간을 신경쓰지 않아도 된다. 

이젠 내 맘대로 변형한 삼각형의 범위만 잘 설정해주면 이 문제는 해결할 수 있다.

 

import kotlin.math.max

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()

    val num = Array(n) { readLine().split(" ").map { it.toInt() }.toIntArray() }

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


    num.mapIndexed { i, a ->
        a.mapIndexed { j, b ->
            triangle[i][j + 1] = b
        }
    }

    for (i in 1 until n + 1) {
        dp[0][i] = triangle[0][i]
    }

    for (i in 1 until n) {
        for (k in 1 until n + 1) {
            dp[i][k] = max(dp[i - 1][k - 1] + triangle[i][k], dp[i - 1][k] + triangle[i][k])
        }
    }

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