[백준] 2156 포도주 시식 c++

 

문제 링크  https://www.acmicpc.net/problem/2156

 

KEY

[백준] 계단오르기와 상당히 유사한 문제이다. 계단오르기 문제는 항상 연속 몇칸이상을 못간다는 등의 제약조건이 있다. 

지금 이 문제 또한 연속 3잔의 포도주를 마실 수 없다는 조건이 있으므로, 현재 시점에서 구할 수 있는 최댓값의 후보를 파악하는 것이 중요하다.

후보는 다음과 같다.

후보1) i-3번째 잔까지의 최댓값 + i-1번째 잔 + i번째 잔

후보2) i-2번째 잔까지의 최댓값 + i번째 잔

후보3) i-1번째 잔까지의 최댓값

다음 후보들 중 최댓값을 구하면 되는 문제이다.

 

두 문제의 차이점

계단오르기 문제는 지금 칸의 점수를 무조건 포함해야 하기 때문에 후보3이 없어야 한다.

하지만 지금 이 문제의 경우 자신을 포함하지 않아도 최댓값이 될 수 있으므로 후보3이 필요하다.

 

Code

 

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
const int MAX = 10001;
int n;
int arr[MAX];
int dp[MAX];
int answer;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    //dp배열 초기화
    dp[0] = arr[0];
    dp[1] = arr[0] + arr[1];
    dp[2] = max(max(arr[0] + arr[2], arr[1] + arr[2]), dp[1]);
 
    for (int i = 3; i < n; i++) {
        dp[i] = max(max(dp[i - 3] + arr[i - 1] + arr[i], dp[i - 2] + arr[i]), dp[i - 1]);
    }
 
    for (int i = 0; i < n; i++) {
        answer = max(answer, dp[i]);
    }
    cout << answer;
}