문제

image.png

image.png

풀이

효주가 가장 많은 포도주를 마실 수 있도록 해야 한다.(아래의 조건을 만족하면서)

- 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
- 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

예를들어, 각각의 잔에 순서대로 6,10,13,9,8,1 만큼의 포도주가 들어 있을때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 33만큼의 포도주를 마셔서 최대의 양을 마시게 된다. 연속으로 3잔을 마실수 없다는 조건을 잘 처리해줘야 한다.

dp[n] 은 n번째잔까지 마신 와인의 최대값
d[n] = max ( d[n-1], d[n-2] + p[n], dn[n-3] + p[n-1] + p[n])

위와 같은 점화식이 나오는 이유를 알아보자.

  • n=2인 경우 3가지 경우로 나눠진다.
6,10
  1. n번째 와인 마시지 않는 경우 (6)
  2. n번째 와인이 연속 1번째 마신 경우 (10)
  3. n번째 와인이 연속 2번째 마신 경우(16)

dp[2] = 16

  • n=3인 경우 3가지 경우로 나눠진다.
6,10,13
  1. n번째잔 와인을 마시지 않는 경우 (16)
  2. n번째잔이 연속 1잔째 마신 경우 (6 + 13)
  3. n번째잔이 연속 2잔째 마신경우 (10 + 13)

와인을 최대로 마셔야 하는 경우를 찾아야 하므로

dp[3] = 23

  • n=4
6,10,13,9
  1. n번째잔 와인을 마시지 않는 경우(23)
  2. n번째 잔이 연속 1잔째 마신 경우(25)
  3. n번째 잔이 연속 2잔째 마신 경우(28)

dp[4] = 28

  • n=5
    6,10,13,9,8
  1. n번째잔 와인을 마시지 않는 경우(28)
  2. n번째 잔이 연속 1잔째 마신 경우(31)
  3. n번째 잔이 연속 2잔째 마신 경우(33)

dp[5] = 33

  • n = 6
    6,10,13,9,8,1
  1. n번째잔 와인을 마시지 않는 경우(33)
  2. n번째 잔이 연속 1잔째 마신 경우(29)
  3. n번째 잔이 연속 2잔째 마신 경우(32)

dp[6] = 33

코드



#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[100001];
int a[100001];
int main () {
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
    }

    dp[1] = a[1];

    for(int i = 2; i <= n; i++) {
        dp[i] = max(max(dp[i-1], dp[i-2] + a[i]), dp[i-3] + a[i-1] + a[i]);
    }
    printf("%d\n",dp[n]);
    return 0;
}