[백준] 2156. 포도주 시식 (Kotlin)

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

2156번: 포도주 시식

 

 

풀이

import java.util.*
import kotlin.math.max

fun main() = with(Scanner(System.`in`)){
    val n = nextInt()
    val grape = Array(n+1){0}
    val dp = Array(n+1){0} // 최대값 저장

    // 헷갈리지 않기 위해 인덱스 1부터 시작
    grape[0] = 0

    // 포도주 잔 입력
    for(i in 1 until grape.size){
        grape[i] = nextInt()
    }

    for(i in dp.indices){
        when (i) {
            0 -> dp[i] = grape[0] // 포도주가 0개 ( 계산과정용 )
            1 -> dp[i] = grape[1] // 첫번째 포도주 마시기
            2 -> dp[i] = grape[1] + grape[2] // 두번째 포도주 마시기
            // 세번째 이상 포도주 마시기
            else -> {
                /**
                 * 1. 안마시는 경우
                 * 2. 1번 연속으로 마시는 경우
                 * 3. 2번 연속으로 마시는 경우
                 */
                dp[i] = max(max(dp[i-1], (grape[i] + dp[i-2])), (grape[i] + grape[i-1] + dp[i-3]))
            }
        }
    }

    println(dp[n])
}

DP 문제로, 점화식을 세우기 어려웠던 문제이다.

DP에 현재 위치에 도달했을 때 가장 많이 마실수 있는 수를 저장한다.

일단, 포도주를 3번 연속 마실수 없으므로 1잔, 2잔이 있는 경우에는 전부 마시는게 최대의 경우다.

 

3잔 이상 있을 경우

1. 안마시는 경우
2. 1번 연속으로 마시는 경우
3. 2번 연속으로 마시는 경우

3가지 경우의 수로 나눠지는데

 

1번의 경우에는 마시지 않았으므로 이전 최대값을 그대로 가져오면 된다.

dp[i] = dp[i-1]

 

2번의 경우에는 연속되지 않고 1번 마신 경우, 즉 이전에 마시지 않았고 지금 마시는 경우를 나타낸다.

따라서 현재의 잔의 양과 이전값을 건너뛴 전전 값의 최대값을 더해주면 된다.

dp[i] = grape[i] + dp[i-2]

 

3번의 경우에는 2회 연속으로 마신 경우, 즉 이전에 마셨고 지금도 마시는 경우이다.

3번연속 마실수 없으므로 2회 전에는 마시지 않았다는 것을 알 수 있고 따라서 2회 전의 값을 건너뛴, 전전전 값의 최대값을 더해준다.

dp[i] = grape[i] + grape[i-1] + dp[n-3]

 

이제 이 세가지 경우 중 가장 큰 수를 구해주어 dp를 구성하고,

dp의 마지막 원소가 최대의 경우이다.