[백준] 2156번 포도주 시식 (C)

문제 주소

백준 2156번 포도주 시식

2156번: 포도주 시식

알고리즘

DP

힌트

dp배열에 그날 포도주를 마셨을 때와 마시지 않았을 때의 최대값을 저장한다.

문제풀이

dp[i][0], dp[i][1]은 각각 i번째까지의 포도주를 마실때 i번째의 포도주를 마셨을 때와 마시지 않았을 때를 의미한다.
dp[i][0]은 i-1번 까지 포도주를 마셨을 때와 마시지 않았을 때 중 더 큰 값이고, dp[i][1]은 연속으로 3번 이상 마시면 안된다는 조건을 고려해야 하기 때문에 전 포도주를 마시지 않고 마셨을 때와 전 포도주를 마시고 연속으로 마셨을 때 중 더 큰 값을 선택하면 된다. 최종적으로 n번째 포도주를 마셨을 때와 마시지 않았을 때의 최대값을 출력하면 된다.

#include<iostream>
using namespace std;
int in[10001];
int dp[10001][2];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>in[i];

    dp[1][1]=in[1];
    for(int i=2;i<=n;i++){
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        dp[i][1]=max(dp[i-2][0]+in[i-1],dp[i-1][0])+in[i];
    }
    cout<<max(dp[n][0],dp[n][1]);
}