BOJ/백준 - 2156 포도주 시식 C++

포도주 시식!!!

3잔을 연속으로 마실 수 없음을 주의하자!

 

첫번째 잔까지 최대 양은 dp[1] = arr[1]

두번째 잔까지 최대 양은 당연히 dp[2] = arr[1]+arr[2]

세번째 잔까지 최대 양은 arr[1]+arr[3] 이거나 arr[2]+arr[3] 이거나 arr[1]+arr[2]이다.

 

N번째 잔까지 마실 때 최대 양은

dp[i] = dp[i-3] + arr[i-1] + arr[i] , dp[i-1] , dp[i-2] + arr[i] 중 최댓값이 된다.

이 점화식을 그대로 구현하면 아래 코드가 된다.

#include <iostream>
#include <algorithm>
 
 
using namespace std;
 
int dp[10001];
int arr[10001];
 
int main(void) {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int N;
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    dp[1] = arr[1];
    dp[2] = arr[1] + arr[2];
 
    for (int i = 3; i <= N; i++) {
        
        dp[i] = max({ dp[i - 2] + arr[i],dp[i - 1], dp[i-3]+arr[i]+arr[i-1] });
        
    }
 
    cout << dp[N];
    return 0;
}