2156번: 포도주 시식 - Kotlin

2156번: 포도주 시식

문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

 

나의 풀이 - 1차 실패

  이 문제는 DP를 이용해야 하는 문제이다. 역시나 가장 먼저 해야할 것은 우리가 최종으로 구해야할 것을 찾는 것이다. 우리가 구할 값은 최대로 마실 수 있는 포도주의 양을 출력하는 것이다. 무조건 마지막 포도주를 먹어야 한다는 법도 없음으로 최종으로 출력해야 하는 값은 dp에 들어있는 값중 최대를 구하면 되겠다.

 

 DP문제가 그렇듯 일단 이 문제도 뒤에서 부터 생각해야 한다. 가장 마지막 숫자부터 생각하자. 주어진 예제의 숫자는 다음과 같다.

 

6 10 13 9 8 1

 

 

 이제 포도주의 양이 1인 잔을 무조건 마셨을 때, 최대 포도주의 양은 얼마인지 생각해보자.

연속해서 3잔의 포도주를 먹을 수 없다는 말은, 최대 2잔의 포도주를 이어서 먹을 수 있다는 것이다. 그럼 우리는 마지막 포도주를 마신 경우를 2가지의 경우로 나눌 수 있다.

 

1. 마지막 포도주와 그 바로 이전 포도주

2. 마지막 포도주와 그 전전 포도주

 

 1번의 경우에는 2번 연속으로 포도주를 먹었기 때문에 강제적으로 전전 포도주인 9를 먹을 수 가 없다. 그래서 이것도 조건에 넣어줘야 한다. 그래서 1번의 조건을 다음과 같이 번경하겠다.

 

 1. 마지막 포도주와 그 바로 이전 포도주, 그리고 전전전 포도주

 

 전전전 포도주는 연속으로 포도주를 먹지 않았기 때문에 고려할 것이 없다.

 

 2번의 경우도 연속으로 포도주를 먹지 않았기 때문에 전전 포도주에 대해서는 고려할 것이 없다. 그래서 해당하는 포도주까지 먹은 최대 값을 바로 넣어주어도 된다. 이제 이를 식으로 나타내면 다음과 같다.

 

 1. a(n) = n 번째 포도주 + n - 1 번째 포도주 + n - 3 번째 포도주까지의 최대값

 2. b(n) = n 번째 포도주 + n - 2 번쨰 포도주까지의 최대값

 

이젠 2가지 경우의 최대를 구하면 된다 그래서 최종 식은 다음과 같다

 

f(n) = max(a(n), b(n))

 

하지만 이 풀이는 실패하였다.

 

import kotlin.math.max

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()

    val num = IntArray(n)

    val dp = IntArray(n)

    for (i in 0 until n) {
        val temp = readLine().toInt()
        num[i] = temp
    }

    dp[0] = num[0]
    if (n > 1)
        dp[1] = num[0] + num[1]
    if (n > 2)
        dp[2] = max(num[0] + num[2], num[1] + num[2])

    for (i in 3 until n) {
        dp[i] = max(dp[i - 3] + num[i - 1] + num[i], dp[i - 2] + num[i])
    }

    println(dp.max())
}

 

 

나의 풀이 - 2차 성공

 이 문제에는 함정이 존재하였다. 위에서 구한 식에서 연속으로 먹지 않아서 고려해도 되지 않아도 되는 포도주의 최대 값을 바로 넣어주었는데, 연속으로 먹는 것 뿐만이 아니라 연속으로 건너 뛰는 경우도 계산을 해야 하였다. 그래서 해당하는 부분을 넣고 반복문을 통해 연속으로 건너 뛸 수 있는 최대값 까지 값을 구하고 dp값도 같이 max에 넣어주어서 문제를 해결하였다.

 

import kotlin.math.max

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()

    val num = IntArray(n)

    val dp = IntArray(n)

    for (i in 0 until n) {
        val temp = readLine().toInt()
        num[i] = temp
    }

    dp[0] = num[0]
    if (n > 1)
        dp[1] = num[0] + num[1]
    if (n > 2)
        dp[2] = max(num[0] + num[2], num[1] + num[2])

	// 수정한 코드
    for (i in 3 until n) {
        for (j in 0 until i - 2) {
            dp[i] = maxOf(dp[i - 3 - j] + num[i - 1] + num[i], dp[i - 2 - j] + num[i], dp[i])
        }
    }

    println(dp.max())
}