[C++] 2156 - 포도주 시식

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

2156번: 포도주 시식

 

 

#include<iostream>
#include<algorithm>
#include<map>
#include<utility>
#include<vector>
#define endl '\n'
#define MAX(a, b) (a > b ? a : b)
 
using namespace std;
 
int dp[10005];
int wine[10005];
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    
    int n;
    cin >> n;
 
    for(int i = 1; i <= n; ++i)
        cin >> wine[i];
 
    dp[1] = wine[1];
    dp[2] = wine[1]+wine[2];
    dp[3] = MAX(wine[1] + wine[3], wine[2]+wine[3]);
    dp[4] = MAX(dp[2] + wine[4], dp[1] + wine[3] + wine[4]);
 
    for(int i = 5; i <= n; ++i)
        dp[i] = MAX(MAX(dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i]),
         MAX(dp[i-4] + wine[i-2] + wine[i], dp[i-4] + wine[i-1] + wine[i] ));
 
    // for(int i = 1; i <= n; ++i)
    //     cout << dp[i] << ' ';
    // cout << endl;
 
    cout << MAX(dp[n-1],dp[n]) << endl;
 
    return 0;
}

 

점화식을 좀더 효율적으로 할 수는 있을지 몰라도

내가 생각하기에 중간에 3개 이상 안먹는 것은 비효율이라 생각하여 다음과 같은 4가지에 대한 식을 세웠고

최종 배열에서 s[n]과 s[n-1]중 최대 값을 출력하게 하여 풀었다.