[알고리즘] 내려가기 (백준 2096번)

2096번: 내려가기

 다이나믹 프로그래밍 문제다. 최소, 최대 값을 묻는 문제인데 이전에도 자주 풀어 본 적이 있는 유형이다.

 

Solution

 우선 max_dp와 min_dp로 나누어서 각각 최대값, 최소값을 구하는 dp 배열로 만든다. 여기서 최적화할 수 있는 방법은, 최대, 최소값을 구하기 위해서는 max_dp[i][3] 과 max_dp[i-1][3] 만 필요하면 되기 때문에 행이 2개만 있으면 된다. 그래서 max_dp, min_dp 에 필요한 원소 개수는 12개만 있으면 된다.

 

1. N만큼 반복문 실행
   1. 입력 받음
   2. max_dp, min_dp를 입력받은 값으로 초기화
   3. i > 0 이상일 때
      1. j == 0 : [BEFORE][0], [BEFORE][1]을 비교한다.
      2. j == 1 : [BEFORE][0], [BEFORE][1], [BEFORE][2]를 비교한다.
      3. j == 2 : [BEFORE][1], [BEFORE][2]를 비교한다.
      4. 각각 최대, 최소값을 구해서 [AFTER][j]에 넣는다.
   4. 최대, 최소값을 다 구했으면 마지막에 AFTER와 BEFORE 값을 바꾼다.
2. 반복문 종료 후 max_dp[AFTER]의 최대값과, min_dp[AFTER]의 최소값을 출력한다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.math.max
import kotlin.math.min

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))

var BEFORE = 0
var AFTER = 1

fun solution() {

    var N = br.readLine().toInt()

    var max_dp = Array(2, {Array(3, {0})})
    var min_dp = Array(2, {Array(3, {0})})

    for(i in 0 until N)
    {
        var strtok = StringTokenizer(br.readLine())

        max_dp[AFTER].forEachIndexed{j, v -> max_dp[AFTER][j] = strtok.nextToken().toInt() }
        min_dp[AFTER].forEachIndexed{j, v -> min_dp[AFTER][j] = max_dp[AFTER][j] }

        if(i > 0)
        {
            //첫번쨰자리 최소값
            if(min_dp[BEFORE][0] < min_dp[BEFORE][1])
                min_dp[AFTER][0] += min_dp[BEFORE][0]
            else
                min_dp[AFTER][0] += min_dp[BEFORE][1]
            //첫번째자리 최대값
            if(max_dp[BEFORE][0] > max_dp[BEFORE][1])
                max_dp[AFTER][0] += max_dp[BEFORE][0]
            else
                max_dp[AFTER][0] += max_dp[BEFORE][1]

            //두번쨰자리 최소값
            var min = Int.MAX_VALUE
            var max = Int.MIN_VALUE

            min_dp[BEFORE].forEach { min = min(min, it) }
            min_dp[AFTER][1] += min

            //두번째자리 최대값
            max_dp[BEFORE].forEach { max = max(max, it) }
            max_dp[AFTER][1] += max


            //세번째자리 최소값
            if(min_dp[BEFORE][2] < min_dp[BEFORE][1])
                min_dp[AFTER][2] += min_dp[BEFORE][2]
            else
                min_dp[AFTER][2] += min_dp[BEFORE][1]

            //세번째자리 최대값
            if(max_dp[BEFORE][2] > max_dp[BEFORE][1])
                max_dp[AFTER][2] += max_dp[BEFORE][2]
            else
                max_dp[AFTER][2] += max_dp[BEFORE][1]
        }

        var temp = AFTER
        AFTER = BEFORE
        BEFORE = temp
    }



    var max = Int.MIN_VALUE
    var min = Int.MAX_VALUE
    max_dp[BEFORE].forEach{ max = max(max, it) }

    min_dp[BEFORE].forEach { min = min(min, it) }
    bw.write("$max $min")

}



fun main() {
    solution()


    br.close()
    bw.close()
}