[C++][BAEKJOON][DP] 2156번 포도주 시식

[문제]

2156번: 포도주 시식

 

[설명]

★이 문제가 DP 인 이유: 현재 값을 구할 때 이전 결과값을 이용할 수 있는 모양이 나오기 때문

•  포도주가 1잔 일 때,
  1잔 모두를 선택해야 최대이다.

 

• 포도주가 2잔 일 때,
  2잔 모두를 선택해야 최대이다.

 

• 포도주가 3잔 일 때,
  3번째 잔을 선택할 경우와 선택하지 않을 경우로 나눌 수 있다.
  이 때, 3번째 잔을 선택하지 않을 경우는 포도주가 2잔 이었을 때 구한 최대값과 같다.
  3번째 잔을 선택했다면, 2번째 잔을 선택하고 1번째 잔을 선택하지 않는 경우와 □ ■ ■, 2번째 잔을 선택하지 않고 1번째 잔을 선택하는 경우 2가지가 있다. ■ □ ■

 

• 포도주가 4잔 일 때,
  4번쨰 잔을 선택할 경우와 선택하지 않을 경우로 나눌 수 있다.
  4번째 잔을 선택하지 않는 경우는 포도주가 3잔 이었을 때 구한 최대값과 같다.
  4번째 잔을 선택하는 경우는 3번째 잔을 선택하고 1번째 잔을 선택하는 경우와(=포도주가 1잔 이었을 때 구한 최대값) ■ □ ■ ■, 3번째 잔을 선택하지 않고 포도주가 2잔 이었을 때 구한 최대값을 이용하는 경우가 있다. ■ ■ □ ■

 

• 포도주가 5잔 일 때,
  5번쨰 잔을 선택할 경우와 선택하지 않을 경우로 나눌 수 있다.
  5번째 잔을 선택하지 않는 경우는 포도주가 4잔 이었을 때 구한 최대값과 같다.
  5번째 잔을 선택하는 경우는 4번째 잔을 선택하고 2번째 잔을 선택하는 경우와(=포도주가 2잔 이었을 때 구한 최대값) □ ■ □ ■ ■, 4번째 잔을 선택하지 않고 포도주가 3잔 이었을 때 구한 최대값을 이용하는 경우가 있다. (□ ■ ■ □ ■), (■ ■ □ □ ■), (■ □ ■ □ ■)

 

즉, 현재 값을 구할 때 이전 결과값을 이용할 수 있는 모양이 나온다.
그리고 위의 과정을 점화식으로 나타내면 다음과 같다.

 

 

• 포도주가 N잔 일 때,
  N번쨰 잔을 선택할 경우와 선택하지 않을 경우로 나눌 수 있다.
  N번째 잔을 선택하지 않는 경우는 포도주가 N-1잔 이었을 때 구한 최대값과 같다.
  N번째 잔을 선택하는 경우는 N-1번째 잔을 선택하고 N-3번째 잔을 선택하는 경우와(=포도주가 N-3잔 이었을 때 구한 최대값), N-1번째 잔을 선택하지 않고 포도주가 N-2잔 이었을 때 구한 최대값을 활용하는 경우가 있다.

D[N] = max(D[N-1], A[N] + A[N-1] + D[N-3],A [N] + D[N-2])

 

[코드]

#include <iostream>
#include <vector>
using namespace std;

void DrinkGrapeJuice(int*, int);
int Max(int, int, int);

int main() {
    int num = 0;
    int grape_juice[10001] = {0,};

    cin >> num;
    for (int i = 1; i <= num; i++) {
        cin >> grape_juice[i];
    }
    DrinkGrapeJuice(grape_juice, num);

    return 0;
}

void DrinkGrapeJuice(int *grape_juice, int num) {
    int dp[10001] = {0,};

    dp[1] = grape_juice[1];
    if (num >= 2) dp[2] = dp[1] + grape_juice[2];

    for (int i = 3; i <= num; i++) {
        dp[i] = Max(dp[i - 1], dp[i - 2] + grape_juice[i], dp[i - 3] + grape_juice[i - 1] + grape_juice[i]);
    }
    cout << dp[num];
}

int Max(int a, int b, int c) {
    return a > b ? (a > c ? a : c) : (b > c ? b : c);
}