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

문제

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

풀이

• 메모이제이션
• 경우의 수를 생각해보자.
• dp[0] 은 (0)
• dp[1] 은 (0 + 1) or (1)
• dp[2] 는 (0 + 1) or (1 + 2) or (0 + 2)
• dp[3] 은 (0 + 1 + 3) or (1 + 2) or (0 + 2 + 3)
• 여기서 (0 + 1 + 3) 은 dp[1] + (3) 으로 대체될 수 있고,
• (1 + 2) 는 dp[2] 로 대체될 수 있고,
• (0 + 2 + 3) 은 dp[0] + (2) + (3) 을오 대체될 수 있으므로,
• dp[3] = maxOf(dp[1] + (3), dp[2], dp[0] + (2) + (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()
}

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