[백준 2096번][Kotlin] 내려가기

https://www.acmicpc.net/problem/2096

2096번: 내려가기

 

 

난이도 : 골드 5
태그 : 다이나믹 프로그래밍, 슬라이딩 윈도우

 

 

설명

이전 값들을 이용하여, 최대값 및 최소값을 구하는 다이나믹 프로그래밍 문제입니다.

 

 

 

소스코드

전체 소스코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer
import kotlin.math.max
import kotlin.math.min

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()

    val arr = Array(n) { Array(3) { 0 } }

    repeat(n) { x ->
        val st = StringTokenizer(br.readLine(), " ")
        repeat(3) { y ->
            arr[x][y] = st.nextToken().toInt()
        }
    }

    val maxDP = Array(n) { Array(3) { 0 } }
    val minDP = Array(n) { Array(3) { 0 } }
    maxDP[0][0] = arr[0][0]
    maxDP[0][1] = arr[0][1]
    maxDP[0][2] = arr[0][2]
    minDP[0][0] = arr[0][0]
    minDP[0][1] = arr[0][1]
    minDP[0][2] = arr[0][2]

    for (i in 1 until n) {
        maxDP[i][0] = arr[i][0] + max(maxDP[i - 1][0], maxDP[i - 1][1])
        maxDP[i][1] = arr[i][1] + max(maxDP[i - 1][0], max(maxDP[i - 1][1], maxDP[i - 1][2]))
        maxDP[i][2] = arr[i][2] + max(maxDP[i - 1][1], maxDP[i - 1][2])

        minDP[i][0] = arr[i][0] + min(minDP[i - 1][0], minDP[i - 1][1])
        minDP[i][1] = arr[i][1] + min(minDP[i - 1][0], min(minDP[i - 1][1], minDP[i - 1][2]))
        minDP[i][2] = arr[i][2] + min(minDP[i - 1][1], minDP[i - 1][2])
    }

    print("${maxDP[n - 1].maxOrNull()!!} ${minDP[n - 1].minOrNull()!!}")
}

 

해당 문제의 전체 소스코드 입니다.

한 부분씩 살펴보겠습니다.

 

 

입력값 세팅과 배열 생성

val br = BufferedReader(InputStreamReader(System.`in`))
val n = br.readLine().toInt()

val arr = Array(n) { Array(3) { 0 } }

repeat(n) { x ->
    val st = StringTokenizer(br.readLine(), " ")
    repeat(3) { y ->
        arr[x][y] = st.nextToken().toInt()
    }
}

val maxDP = Array(n) { Array(3) { 0 } }
val minDP = Array(n) { Array(3) { 0 } }
maxDP[0][0] = arr[0][0]
maxDP[0][1] = arr[0][1]
maxDP[0][2] = arr[0][2]
minDP[0][0] = arr[0][0]
minDP[0][1] = arr[0][1]
minDP[0][2] = arr[0][2]

해당 문제의 전체 소스코드 입니다.

각 층의 값들을 저장하는 배열 arr와,

최대값을 구하기 위해 사용할 maxDP 배열,

최소값을 구하기 위해 사용할 minDP 배열을 생성합니다.

 

maxDP[0]과 minDP[0]에는 arr[0]으로 초기값을 설정해줍니다.

 

 

최대값, 최소값 구하기

for (i in 1 until n) {
    maxDP[i][0] = arr[i][0] + max(maxDP[i - 1][0], maxDP[i - 1][1])
    maxDP[i][1] = arr[i][1] + max(maxDP[i - 1][0], max(maxDP[i - 1][1], maxDP[i - 1][2]))
    maxDP[i][2] = arr[i][2] + max(maxDP[i - 1][1], maxDP[i - 1][2])

    minDP[i][0] = arr[i][0] + min(minDP[i - 1][0], minDP[i - 1][1])
    minDP[i][1] = arr[i][1] + min(minDP[i - 1][0], min(minDP[i - 1][1], minDP[i - 1][2]))
    minDP[i][2] = arr[i][2] + min(minDP[i - 1][1], minDP[i - 1][2])
}

 

해당 문제에서는 수직, 바로 옆 대각선 방향으로만 움직일 수 있으므로,

 

maxDP의 경우 바로 이전 값의 수직, 바로 옆 대각선 방향 값들 중 큰 값과 현재 값(arr[i])를 더합니다.

minDP의 경우 위와 반대로 작은 값과 현재 값을 더하면 됩니다.

 

 

출력

print("${maxDP[n - 1].maxOrNull()!!} ${minDP[n - 1].minOrNull()!!}")

 

maxDP 배열의 n-1 번째 3개의 값중 가장 큰 것과,

minDP 배열의 n-1 번째 3개의 값중 가장 작은 것을 출력합니다.

 

 

 

후기

다이나믹 프로그래밍을 배울 때, 예제로 많이 사용되는 문제중 하나인

바로 다음 칸과 그 옆칸으로만 움직일 수 있는 유형의 문제 입니다.

 

유튜브 강의와 알고리즘 책을 보며 다이나믹 프로그래밍을 처음 배울때,

예제로 나왔던 문제와 같은 유형의 문제를 보니 반갑네요.