[BOJ] 포도주 시식

[BOJ] 포도주 시식

Problem URL : 포도주 시식

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

int arr[10001];
int dp[10001];

int main() {
    int n;
    scanf("%d",&n);

    for (int i = 1; i <= n; i++)
        scanf("%d", arr + i);

    dp[1] = arr[1];
    dp[2] = arr[1] + arr[2];
    for (int i = 1; i <= n; i++) {
        /*포도주 i,(i-1),(i-2)를 기준으로 i만 포함하는 경우, i와 (i-1) 2개 포함하는 경우, 
        (i-1)과 (i-2) 2개 포함하는 경우 3가지 중에서 최댓값을 dp[i]로 한다. */
        dp[i] = max(dp[i - 1], max(dp[i - 2], dp[i - 3] + arr[i - 1]) + arr[i]);
    }

    printf("%d", dp[n]); // dp[x] > dp[x-1]이 항상 성립한다.
    return 0;
}