[백준 2156] 포도주 시식

0. 제목

• 백준 2156 포도주 시식
• BOJ 2156 포도주 시식
• C++ 2156 포도주 시식

---

1. 문제

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

---

2. 풀이

• DP 방식을 이용하였다.
• 연속하여 3잔을 마실 수 없다는 것이 핵심이다.
• 먼저 점화식에 사용될 초기값들 dp[1], dp[2], dp[3] 을 구한다.
• dp[i] 를 구할 때, 총 세가지 경우가 나올 수 있다.
• 먼저 마지막 포도주 잔을 선택했을 경우 두가지 경우가 나오는데, 전 포도주를 마신 경우(dp[i-3] + arr[i-1] + arr[i])와 전 포도주를 안마신 경우(dp[i-2] + arr[i])이다.
• 마지막 포도주 잔을 선택하지 않았을 경우는 그 전에 잔을 선택한 경우(dp[i-1])에 최대값이 된다.
• 따라서 이 세가지 중에 최대값이 정답이다.

---

3. 코드

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int n;
    int arr[10001];
    int dp[10001];
    
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    dp[1] = arr[1];
    dp[2] = arr[1] + arr[2];
    dp[3] = max(arr[1]+arr[2], (max(arr[1], arr[2]) + arr[3]));
    for(int i = 4; i <= n; i++)
        dp[i] = max(dp[i-1], max(dp[i-2], dp[i-3] + arr[i-1]) + arr[i]);
    cout << dp[n] << '\n';
    return 0;
}