[BOJ/C++] 포도주 시식(2156번)

1. 개요

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

2156번: 포도주 시식

1-1. 설명

효주는 포도주 시식회에 갔다. 그 곳에서, 테이블 위 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 포도주를 시식하려는데 두가지 규칙이 존재한다.

 - 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야하며, 마신 후에는 원래 위치에 다시 놓아야 함

 - 연속으로 놓여있는 3잔 모두 마실 수 X

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

1-2. 제한 사항

 - 첫 줄에 포도주 잔의 개수 N이 주어지며, N은 1 이상 10,000 이하

 - 둘째 줄부터 N+1번째 줄까지 포도주 잔이 들어있는 포도주 양이 주어지며, 포도주 양은 1,000 이하 음이 아닌 정수

---

2. 구현

2-1. 풀이

다이나믹 프로그래밍 방식을 이용했다. 총 3가지 경우의 수를 고려했는데, 1잔과 2잔, 2잔과 1잔, 2잔 이렇게 세 가지 방식을 고려하여 가장 큰 수를 선택해 dp에 저장해주었다. 그렇게 어렵지 않아 점화식도 금방 떠올랐다. 

2-2. 코드

#include <iostream>
#include <algorithm>
using namespace std;

constexpr size_t MAX = 10001;
int drinks[MAX], dp[MAX];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> drinks[i];

    dp[1] = drinks[1];
    dp[2] = drinks[1] + drinks[2];
    for (int i = 3; i <= N; i++) {
        dp[i] = max({ dp[i - 1], dp[i - 3] + drinks[i - 1] + drinks[i], dp[i - 2] + drinks[i] });
        // XOOX -> 2잔
        // OXOO -> 1잔, 2잔
        // OOXO -> 2잔, 1잔
    }
    
    cout << dp[N];
    return 0;
}