백준 2156 포도주 시식

#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

long long dp[10002];
int main()
{
  int n;
  int podo[10002];

  cin>>n;
  for (int i = 1; i <= n; i++)
  {
    cin>>podo[i];
  }
  dp[0] = 0;
  dp[1] = podo[1];
  dp[2] = podo[2] + podo[1];

  for (int i = 3; i <= n; i++)
  {
    dp[i] = max(dp[i-3] + podo[i-1] + podo[i], dp[i-2] + podo[i]);
    dp[i] = max(dp[i], dp[i-1]);
  }

  cout<<dp[n];
  return 0;
}

n 번째 포도주를 들고 있을 때, 이 녀석을 마실지 말지를 고민하는 방식으로 dp 식을 작성해 보았다.

먼저, n-3 번째 였을 때 dp의 결과에 포도주 n-1, n  을 더하는 방법이 한가지 있고,

두번째 방식으로는, n-2 반째 까지의 dp 에 지금 n 번째 포도주 양을 더하는 방식이 또 한가지 있겠다.

 

이게 다가 아니다!

지금까지 n 번째 포도주를 무조건 마시는 경우를 구한 것이기 때문에, 아예 안마신 경우가 더 큰 경우를 고려해야 한다.

따라서 dp[n-1] , dp[n] 을 서로 비교해 더 큰 걸 선택하도록 하자!