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

 

다이나믹 프로그래밍 문제입니다.

 

연속으로 3개의 포도주를 마시지 않으면서 최대한 많이 포도주를 마셨을때의 값을 찾는 문제입니다.

1. 현재 포도주를 안 먹었을 때

2. 현재 포도주를 먹지 않았고 이전 포도주를 먹었을 때

3. 현재 포도주와 이전 포도주 둘 다 먹었을 때

이렇게 3가지로 나타낼 수 있습니다.

 

코드로 작성하면

memo[i] = memo[i-1];

memo[i] = memo[i-2] + drink[i];

memo[i] = memo[i-3] + drink[i-1] + drink[i-2];

 

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

int memo[10010];
int drink[10010];
void init()
{
   for (int i = 0; i < 10010; ++i) {
      drink[i] = 0;
      memo[i] = 0;
   }
}

int main(int argc, char *argv[])
{
   init();
   int n;
   cin >> n;

   for (int i = 0; i < n; ++i) {
      cin >> drink[i];
   }
   memo[0] = drink[0];
   memo[1] = drink[0] + drink[1];
   for (int i = 2; i < n; ++i) {
      memo[i] = max(memo[i - 1], max(memo[i - 2] + drink[i], memo[i - 3] + drink[i - 1] + drink[i]));
   }

   cout << memo[n - 1];
   return 0;
}