[백준] 2156번: 포도주 시식

문제

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

풀이

• 메모이제이션
• 4번째 포도주를 마신다고 가정해보자.
• 선택지는 3가지가 있다.
• 1. 1번째, 2번째 4번째
• 2. 1번째, 3번째 4번째
• 3. 2번째, 3번째
• 마지막 경우의 수를 처음에 놓쳤는데, 2번째 3번째 수가 매우 큰 수라면 충분히 가능하기 때문에 총 3가지 경우의 수를 고려해주어야 한다.

fun drinkMaxGrape(n: Int, grapes: List<Long>): Long {
    val dp = LongArray(n) { 0 }
    dp[0] = grapes[0]
    if (n == 1) return dp[0]
    dp[1] = grapes[0] + grapes[1]
    if (n == 2) return dp[1]
    dp[2] = maxOf(grapes[0] + grapes[2], grapes[1] + grapes[2], dp[1])
    if (n == 3) return dp[2]
    for (i in 3 until n) {
        dp[i] = maxOf(dp[i - 1], dp[i - 3] + grapes[i - 1] + grapes[i], dp[i - 2] + grapes[i])
    }
    return dp.maxOf { it }
}

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val n = br.readLine().toInt()
    val grapes = mutableListOf<Long>()
    repeat(n) {
        grapes.add(br.readLine().toLong())
    }
    bw.write("${drinkMaxGrape(n, grapes)}")
    bw.close()
    br.close()
}

더 좋은 풀이 있으면 댓글 달아주세요!!!