[백준] 2156번 포도주 시식

문제

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

풀이과정

DP[i] 를 i번째 포도주 잔까지 최대로 마실 수 있는 양이라 한다.

이 문제는 3가지의 경우로 나누어서 생각한다.

1. 현재 포도주를 마시지 않는 경우 

2. 현재 포도주를 마시고 이전 포도주를 마시지 않는 경우 ( o x o )

3. 현재 포도주와 이전 포도주를 마시는 경우 ( x o o )

3가지의 경우 중 가장 큰 값을 찾는다.

소스코드

#include <iostream>
#include <algorithm>
 
using namespace std;
int DP[10001], wine[10001];
 
int main()
{
    int n;
 
    cin >> n;
 
    for (int i = 1; i <= n; i++)
    {
        cin >> wine[i];
    }
 
    for (int i = 1; i <= n; i++)
    {
        int ans = 0;
        if (i <= 2) DP[i] = wine[i] + wine[i - 1]; // DP[1] , DP[2] 초기화
        ans = max(DP[i - 1], // 현재 포도주를 마시지 않는 경우
                max(wine[i] + DP[i - 2],  // 현재 포도주를 마시고 이전 포도주를 마시지 않는 경우
                    DP[i - 3] + wine[i] + wine[i - 1])); // 현재 포도주와 이전 포도주를 마시는 경우
        DP[i] = ans;
    }
 
    cout << DP[n];
 
    return 0;
}