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

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

2156번: 포도주 시식

동적계획법으로 접근하였습니다. dp[i] 에 대해 i 번 째 포도주 까지에 대해 최대로 마실 수 있는 포도주의 양 이라고 정의했습니다. dp[i] 가 최대가 되기 위해서는 3가지 경우를 비교해주어야 합니다.

 

1. 현재의 포도주를 마시고 이전 포도주를 마시지 않은 경우

   cup[i] + dp[i-2]
   

2. 현재의 포도주를 마시고 이전 포도주를 마신 경우

   cup[i] + cup[i-1] + dp[i-3]
   

3. 현재의 포도주를 마시지 않은 경우

   dp[i-1]
   

    

#include <iostream>

using namespace std;

int max(int a,int b,int c){
    return max(max(a,b), c);
}

int main(){
    int n;
    cin >> n;
    int cup[10001];
    int dp[10001];
    
    for (int i=1;i<=n;i++){
        cin >> cup[i];
    }
    dp[0] = 0;
    dp[1] = cup[1];
    dp[2] = cup[1] + cup[2];
    for (int i=3;i<=n;i++){
        dp[i] = max(dp[i-3]+cup[i]+cup[i-1], dp[i-2]+cup[i], dp[i-1]);
    }
    
    cout << dp[n] << "\n";
    
    return 0;
}