[BOJ] 백준 2156. 포도주 시식

▶문제설명

[BOJ] 백준 2156. 포도주 시식

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

▶Hint

---

DP 문제이다.

[규칙]

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

규칙에 따르면, 하나의 잔 기준으로 세 가지 경우로 나눌 수 있다.

1. 이전 잔의 포도주를 마시고 현재 잔의 포도주를 마시는 경우

: A = dp[N-3] + glasses[N-1] + glasses[N];

[N-3]	[N-2]	[N-1]	[N]
N-3번째 잔까지의 최대값		이 잔을 마시고	이 잔을 마심

2. 이전 잔의 포도주를 마시지 않고 현재 잔의 포도주를 마시는 경우

: B = dp[N-2] + glasses[N];

[N-2]	[N-1]	[N]
N-2번째 잔까지의 최대값		이 잔을 마심

3. 현재 잔의 포도주를 마시지 않는 경우

: C = dp[N-1]

[N-2]	[N-1]	[N]
	N-1번째 잔까지의 최대값	N-1번째 잔까지의 최대값

이 세 가지 경우를 비교해서  가장 큰 경우를 dp테이블에 저장하면 각 위치에서 취할 수 있는 최대값을 구할 수 있다.

: dp[N] = max(max(A, B), C);

한 마디로 정리하면 dp[N]의 위치에

N-3번째 잔까지의 최대값 + N-1번째 잔 + N번째 잔

N-2번째 잔까지의 최대값 + N번째 잔

N-1번째 잔까지의 최대값

세 개의 값 중에 가장 큰 값을 저장하도록 구현하면 된다.

[초기값]

dp[0] = 0;

dp[1] = glasses[1];

dp[2] = glasses[1] + glasses[2];

▶Solution