[BOJ/C++] 2156번 : 포도주 시식

풀이

DP 사용. DP배열 N번째에 최대 양이 나오게 구현.

 

1. i번째 포도주를 먹고 i-1번째 포도주를 먹은 경우

2. i번째 포도주를 먹고 i-2번째 포도주를 먹은 경우

3. i번째 포도주를 먹지 않고 i-1번째 포도주를 먹은 경우

 

코드

 

#include <stdio.h>
#include <iostream>
#include <cstdio>
using namespace std;
 
 
int main(){
 
 
    int n;
    int data[10001], dp[10001];
    scanf("%d", &n);
 
    for(int i=1;i<=n;i++){
        scanf("%d", &data[i]);
    }
 
    dp[1]=data[1];
    dp[2]=data[1]+data[2];
 
 
    for(int i=3;i<=n;i++){
        dp[i]=max(data[i]+data[i-1]+dp[i-3], max(data[i]+dp[i-2], dp[i-1]));
    }
 
    printf("%d", dp[n]);
 
}