백준 2156 포도주 시식 Java: 마지막 잔을 고르지 않는 DP 점화식

이 문제를 처음 봤을 때는 계단 오르기처럼 “현재 잔을 마신다”는 전제로 점화식을 세웠다. 하지만 포도주 시식은 마지막 잔을 반드시 마셔야 한다는 조건이 없다. 이 차이를 놓쳐 두 번 틀렸고, 세 번째에는 n < 3을 처리하지 않아 배열 범위를 벗어났다. 네 번째 시도에서야 통과했다.

DP 문제를 꾸준히 풀다 보니 점화식을 찾는 과정 자체가 조금씩 재미있어진다. 이번 문제의 핵심은 각 위치에서 “마신다”만 따지지 않고, 마시지 않는 경우까지 상태에 넣는 것이었다.

문제를 어떻게 상태로 바꿀까

포도주 잔은 일렬로 놓여 있고 연속으로 세 잔을 마실 수 없다. 각 잔의 양은 0 이상 1,000 이하이고, 잔의 수 n은 최대 10,000이다.

dp[i]를 1번부터 i번 잔까지 고려했을 때 마실 수 있는 포도주의 최댓값으로 정의한다. 그러면 i번째 잔을 마실 수도 있고, 마시지 않을 수도 있다.

경우	선택	누적 최댓값
i번째 잔을 마시지 않음	i 제외	dp[i - 1]
i번째 잔만 이어서 마심	i - 1 제외, i 선택	dp[i - 2] + wine[i]
i-1, i번째 잔을 연속으로 마심	i - 2 제외, i - 1과 i 선택	dp[i - 3] + wine[i - 1] + wine[i]

따라서 점화식은 다음과 같다.

dp[i] = max(
    dp[i - 1],
    dp[i - 2] + wine[i],
    dp[i - 3] + wine[i - 1] + wine[i]
)

첫 번째 항이 빠지면 “i번째 잔을 반드시 마신다”는 잘못된 전제가 생긴다. 내가 처음 두 번 틀린 이유도 이 경우를 상태에 넣지 않았기 때문이다.

경계값부터 안전하게 만든다

n이 1이나 2일 때도 같은 코드가 동작하도록 0번 위치를 값 0인 가상 상태로 둔다.

dp[0] = 0
dp[1] = wine[1]
dp[2] = wine[1] + wine[2]  // n이 2 이상일 때만

포도주의 양이 0인 잔도 별도 분기가 필요 없다. 점화식의 max가 자연스럽게 마시지 않는 선택을 포함한다. 최댓값도 10,000 × 1,000 = 10,000,000을 넘지 않으므로 Java의 int로 충분하다.

예제 6 / 10 / 13 / 9 / 8 / 1에서는 다음처럼 계산된다.

i	포도주 양	dp[i]
1	6	6
2	10	16
3	13	23
4	9	28
5	8	33
6	1	33

마지막 값이 이전 값과 같은 것은 6번째 잔을 마시지 않는 편이 최적이기 때문이다.

Java 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] wine = new int[n + 1];
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            wine[i] = Integer.parseInt(br.readLine());
        }

        dp[1] = wine[1];
        if (n >= 2) {
            dp[2] = wine[1] + wine[2];
        }

        for (int i = 3; i <= n; i++) {
            int skipCurrent = dp[i - 1];
            int drinkCurrent = dp[i - 2] + wine[i];
            int drinkTwoInARow = dp[i - 3] + wine[i - 1] + wine[i];

            dp[i] = Math.max(skipCurrent, Math.max(drinkCurrent, drinkTwoInARow));
        }

        System.out.println(dp[n]);
    }
}

각 잔을 한 번씩만 계산하므로 시간 복잡도는 O(n), 배열 두 개를 사용하므로 공간 복잡도는 O(n)이다. 직전 세 상태와 포도주 양만 보관하면 O(1) 공간으로 줄일 수도 있다. 다만 처음 점화식을 검증할 때는 상태가 그대로 보이는 배열 풀이가 실수를 찾기 쉽다.

확인할 입력은 최소 크기 n = 1, n = 2, 중간에 0이 있는 경우, 마지막 잔을 마시지 않는 편이 최적인 경우다. 비슷해 보여도 마지막 계단을 반드시 밟아야 하는 백준 2579 계단 오르기와 비교하면 상태 정의의 차이가 더 잘 보인다. DP 코드의 실행 횟수를 세는 문제는 백준 24416 피보나치 수 1에서 이어서 볼 수 있다.

참고 자료

• 백준 2156 포도주 시식