[백준] 2156 - 포도주 시식

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

2156번: 포도주 시식

전형적인 dp문제이다. dp[i]는 i번째 포도주에 도달했을때 가장 많이 마신 양이다. 그렇다면 두 가지 방법으로 나뉠 수 있다. 첫번째로 i번째를 마셨을때이다. 이를 마셨다면 또 두가지로 나뉜다. 이전 포도주를 마셨냐 안 마셨냐이다. 마셨다면 3번 연속으로 못 마시기에 dp[i - 3]과 이전 포도주, 현재 포도주를 다 더해준다. 이전 포도주를 안 마셨다면 dp[i - 2]와 현재 포도주를 더해준다. 그리고 마지막으로 안 마셨을때를 고려해 dp[i - 1]까지 비교해 총 3가지를 비교해 최댓값을 대입한다.

#include <iostream>
#define MAX 10001
using namespace std;

int dp[MAX], arr[MAX];
int n;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

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

    dp[0] = 0;
    dp[1] = arr[1];
    dp[2] = arr[1] + arr[2];

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

    cout << dp[n] << "\n";
    return 0;
}