BOJ 2156 포도주 시식

boj 2156 포도주 시식

포도주 잔을 마시는 경우를 맨 마지막 포도주 잔의 상태에 따라 나눌 수 있다.

1. 맨 마지막 포도주 잔을 안마시는 경우
2. 맨 마지막 포도주 잔을 마시는데, 그 잔이 연속된 첫번째 잔인 경우
3. 맨 마지막 포도주 잔을 마시는데, 그 잔이 연속된 두번째 잔인 경우

그림으로 표현하면 다음과 같다.

arr는 포도주 잔의 양을 담는 배열이고, D[i]는 i번째 잔까지 포도주를 최대로 마시는 양으로 테이블을 정한다.

1. D[i] = D[i-1]
2. D[i] = D[i-2] + arr[i]
3. D[i] = D[i-3] + arr[i-1] + arr[i]

위 세 가지를 비교해서 가장 큰 값을 D[i]로 결정하면 된다. 코드로 구현해보자.

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

int n;
int D[10005];
int arr[10005];

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];

    D[1] = arr[1];
    D[2] = arr[1] + arr[2];
    for (int i = 3; i <= n; i++)
    {
        D[i] = max(D[i - 1], D[i - 3] + arr[i - 1] + arr[i]);
        D[i] = max(D[i], D[i - 2] + arr[i]);
    }
    cout << D[n];
}