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

출처 : 2156번: 포도주 시식 (acmicpc.net)

2156번: 포도주 시식

풀이 방법

현재 인덱스 포도주를 기준으로 몇 번 연속인지 계산하면 문제를 쉽게 풀이할 수 있다.

0번째 연속인 경우 dp[i] = dp[i-1] // i번째 포도주를 마시지 않는 경우

1번째 연속인 경우 dp[i] = dp[i-2] + wine[i] // i-2 번째 dp에서 i-1번째 포도주를 건너뛰고 i번째 포도주를 마신 경우

2번째 연속인 경우 dp[i] = dp[i-3] + wine[i-1] + wine[i]  //i-3 dp에서 i-2 번째 포도주를 건너뛰고 i-1번째 포도주를 마시고 i번째 포도주를 마신 경우

3가지 경우 중 최대 값을 dp[i]에 넣어 주면 된다.

1번째 2번째 연속인 경우에서 포도주를 건너뛰는 이유는 이전 dp에서 연속되는 경우를 피하기 위해서 한번 건너뛰고 다음 포도주를 마신 거다

//12865
#include <bits/stdc++.h>
using namespace std ;

int n;
int dp[10001];
int wine[10001] = {0, };



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