백준 1932번: 정수 삼각형

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

문제 풀이

DP

prev = 이전 층까지의 경로의 최대 합

cur = 현재 층까지의 경로의 최대 합

위 층에서 대각선 왼쪽에서 왔을때의 최대 합 prev[j]와 대각선 오른쪽에서 왔을 때의 최대 합 prev[j - 1] 중 더 큰 값과 현재 칸의 수를 더하면 현재 칸으로 도달하는 경로의 최대 합이 된다.

따라서 cur[j] = max(prev[j], prev[j - 1]) + 현재 값이 되므로 이 식에 따라 마지막 층까지 계산하고 합의 최댓값을 찾아 출력하면 정답

풀이 설명

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

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

아래층으로 내려갈 때 대각선 왼쪽 또는 대각선 오른쪽으로만 이동할 수 있다고 했으므로 한 칸에 도달하려면 위 층에서 대각선 왼쪽 또는 대각선 오른쪽의 칸에서 이동해야 한다. 따라서 대각선 왼쪽에서 오는 것이 더 합이 큰지, 오른쪽에서 오는 것이 더 합이 큰지를 확인하면 된다.

이는 위의 층에서부터 한 층을 내려갈때마다 누적이 되므로 DP를 사용해 나타낼 수 있다. prev를 이전 층까지의 경로의 최대 합, cur를 현재 층까지의 경로의 최대 합으로 정의하고 인덱스를 그 층에서의 몇번째 숫자인지를 나타내도록 하면 된다.

그렇게 인덱스로 층에서 몇번째인지 나타내도록 하면 현재 층의 대각선 왼쪽의 위 층의 번호는 현재 층의 번호보다 1 작고, 대각선 오른쪽의 위 층의 번호는 현재 층의 번호와 같게 된다. 또한 현재 층의 맨 첫번째 번호는 항상 대각선 오른쪽의 위 층에서만 올 수 있으므로 예외 처리를 해줘야 한다.

이에 따라 첫 층에서부터 다음 층으로 내려갈 때 어느 칸에서 내려오는 것이 합이 더 커지는지 확인해 더 큰 값을 저장하는 방식으로 마지막 층까지 값을 누적시킨다. 그러면 prev에 마지막 칸에 도달하는 경로의 최대 합이 저장되므로 이 배열 내에서 최댓값을 찾으면 구하는 값이 나오므로 이를 출력하면 정답이 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run{
    fun nextInt(): Int{
        nextToken()
        return nval.toInt()
    }
    val n = nextInt()
    val prev = IntArray(n)
    val cur = IntArray(n)
    for(i in 0 until n){
        for(j in 0..i){
            if(j != 0){
                cur[j] = maxOf(prev[j], prev[j - 1]) + nextInt()
            } else {
                cur[j] = prev[j] + nextInt()
            }
        }
        cur.copyInto(prev)
    }
    var max = 0
    for(i in 0 until n){
        max = maxOf(max, prev[i])
    }
    println(max)
}