백준 - 1932 : 정수 삼각형(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/1932

 

[문제 설명]

정수삼각형을 내려가면서 숫자를 더할 때 가장 큰 수는 몇이 될까요?

 

[접근 방법]

무조건 모든 경우를 확인해야 하는 문제입니다. 그 층에서 최댓값이더라도 다음 층에 수에 따라 결과가 바뀔 수 있기 때문입니다.

반례 설명

결국 마지막 숫자까지 확인하지 않으면 최댓값으로 확정할 수 없는 문제입니다.

그렇다면 이제 탐색하는 방법을 정해야 합니다. dfs나 bfs 둘다 상관 없고, 위에서 시작하든 아래서 시작하든 상관 없습니다.

저는 위에서 아래로 탐색을 했습니다.

모든 요소를 탐색하므로 시간복잡도는 O(n), 공간복잡도 또한 O(n)이 되겠습니다.

 

[Kotlin 코드]

fun main() {
    var answer = Int.MIN_VALUE
    // 삼각형 높이 n(1 ≤ n ≤ 500)
    val n = readln().toInt()
    // 행은 depth - 1, col은 각 층의 숫자들
    val triangle = Array(n) { readln().split(" ").map { it.toInt() }.toIntArray() }
    var size = 0
    // 각 층까지의 합을 답을 배열
    val dp = Array(n) { IntArray(++size) }
    // 삼각형의 맨 꼭대기를 초기화
    dp[0][0] = triangle[0][0]
    // 최고층을 기준으로 아래층에 누적 값을 저장.
    for (level in 0 until triangle.size - 1) {
        for (cIdx in triangle[level].indices) {
            // 왼쪽
            dp[level + 1][cIdx] = dp[level + 1][cIdx].coerceAtLeast(dp[level][cIdx] + triangle[level + 1][cIdx])
            // 오른쪽
            dp[level + 1][cIdx + 1] = dp[level + 1][cIdx + 1].coerceAtLeast(dp[level][cIdx] + triangle[level + 1][cIdx + 1])
        }
    }

    // 마지막 층에 최댓값을 구한다.
    dp[n - 1].forEach { it ->
         answer = answer.coerceAtLeast(it)
    }
    println(answer)
}

다른 사람들 답을 보니 아래에서 위로 탐색하는 경우가 꽤 있었습니다.

아래에서 위로 탐색할 경우 결국 맨 꼭대기가 최댓값이 되므로 따로 최댓값을 구할 필요가 없다는 장점이 있습니다.