백준 2156번: 포도주 시식 (Kotlin)

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

2156번: 포도주 시식

 

풀이

1 <= n <= 10,000이라서 모두 탐색하면 시간 초과가 난다. 풀어보면 어떻게 과거의 모든 경우의 수를 예측해서 문제를 해결하지 싶은데, 이런 경우에는 다이나믹 프로그래밍을 사용할 때가 많았다.

 

나는 다이나믹 프로그래밍 문제를 다음과 같은 절차로 해결한다.

 

1. 반복문에서 사용할 점화식을 구성하기 위해 함수를 정의한다.

-> dp[i]: 포도주가 i번째 까지 있을 때, 조건을 만족하는 최대 포도주 양

2. 함수의 초기 값을 설정한다.

-> dp[0] = 0, dp[1] = wine[1], dp[2] = wine[1] + wine[2] (포도주 인덱스는 1부터 시작하도록 세팅)

3. 초기 값을 기반으로 모든 경우의 수를 커버할 수 있는 점화식을 구한다.

-> dp[i] =

{

 if (i번째 와인을 마시지 않는다) dp[i-1] 

 if (i번째, i-1번째 와인을 마시고, i-2는 마시지 않는다) wine[i] + wine[i-1] + dp[i-3] 

 if (i번째, i-2번째 와인을 마시고, i-1은 마시지 않는다) wine[i] + dp[i-2]

}

 

이렇게 반드시 조건을 만족시키게 점화식을 구성하고, 초기 값부터 점화식을 만족하도록 설정하면 모든 항이 조건을 만족하게 된다.

그리고 점화식을 구성하면서 i-3까지 인덱스를 봐야 하길래, 3번째 포도주부터 반복문을 돌리기 위해 포도주 인덱스를 1부터 시작했다. 

 

그리고 i를 3 ~ n까지 반복문을 돌려서 dp 값을 구하면, dp[n]이 답이 된다.

 

코드

import kotlin.math.max

fun main() {
    val n = readLine()!!.toInt()
    val wines = IntArray(n+2)
    val dp = IntArray(n+2)
    
    // 포도주 인덱스 1부터 시작
    repeat(n){ i ->
        wines[i+1] = readLine()!!.toInt()
    }

    // 초기값 설정
    dp[1] = wines[1]
    dp[2] = wines[1] + wines[2]
    for (i in 3..n){
        // 점화식
        val maxWithCurrentWine 
            = max(dp[i-3] + wines[i-1] + wines[i], dp[i-2] + wines[i]) // i번째 와인을 마시는 경우 중 최대 값 
        dp[i] 
            = max(dp[i-1], maxWithCurrentWine) // i번째 와인을 마시는 or 안마시는 경우 중 최대 값
    }

    println(dp[n])
}