🍷 백준 2156번 - 포도주 시식

🔗 포도주 시식

---

📌 문제 설명

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

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

효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하자.

---

🧩 예제 입력 및 출력

입력

6
6
10
13
9
8
1

출력

33

---

💡 문제 핵심

• 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 한다.
• 연속으로 3잔을 마실 수 없다.
• 마실 수 있는 포도주의 최대 양을 구해야 한다.

---

🔍 풀이 아이디어

✅ 동적 계획법 (DP)

이 문제는 이전 상태를 기반으로 현재 상태를 결정하는 동적 계획법(DP)을 활용하여 해결할 수 있습니다.

• dp[i]: i번째 포도주 잔까지 고려했을 때 마실 수 있는 포도주의 최대 양

점화식

dp[i] = max(
dp[i - 1],                             // 현재 잔을 마시지 않는 경우
dp[i - 2] + arr[i],                    // 이전 잔을 건너뛰고 현재 잔을 마시는 경우
dp[i - 3] + arr[i - 1] + arr[i]        // 전전 잔 마시고, 이전 + 현재 잔을 마시는 경우
)

---

👣 예제 시뮬레이션

입력: 6 10 13 9 8 1

• dp[1] = 6
• dp[2] = 6 + 10 = 16
• dp[3] = max(16, 6 + 13, 0 + 10 + 13) = 23
• dp[4] = max(23, 16 + 9, 6 + 13 + 9) = 28
• dp[5] = max(28, 23 + 8, 16 + 9 + 8) = 33
• dp[6] = max(33, 28 + 1, 23 + 8 + 1) = 33

👉 최종 답: 33

---

✅ 자바 코드

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

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[] arr = new int[N + 1];
		int[] dp = new int[N + 1];

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

		dp[1] = arr[1];
		if (N > 1) {
			dp[2] = arr[1] + arr[2];
		}
		for (int i = 3; i <= N; i++) {
			dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i]));
		}
		System.out.println(dp[N]);
	}
}

🧠 배운 점

• 동적 계획법(DP)은 이전 결과를 활용하여 현재 문제를 해결하는 데 효과적이다.
• 조건을 만족하는 최대/최소값을 구해야 할 때는 DP를 떠올리자.
• 문제에서 주어진 조건(연속으로 3잔을 마실 수 없음)을 잘 고려하여 점화식을 세우는 것이 중요하다.