백준 2156번 포도주 시식

🔒[문제 url]

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

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#define <algorithm>
using namespace std;

int n;
int grape[10001];
int dp[10001];

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> grape[i];
}



void SOLVE()
{
    // 초기 작업
    dp[1] = grape[1];
    dp[2] = grape[1] + grape[2];

    // Bottom Up Dynamic Programming
    for (int i = 3; i <= n; i++)
    {           // 세번째 전 포도주까지의 최대값과 현재와 이전의 것을 마시는 경우
        dp[i] = max(dp[i - 3] + grape[i - 1] + grape[i],
                // 두번째 전 포도주까지의 최대값과 현재 것을 마시는 경우
                    max(dp[i - 2] + grape[i],
                // 이전 포도주까지의 최대값과 현재 것을 마시지 않는 경우
                    dp[i - 1]));
    }
    cout << dp[n];
}


int main()
{
    INPUT();

    SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.