(2156) 포도주 시식

https://www.acmicpc.net/problem/2156

단계별로 풀어보기

21단계(동적 계획법 1) 11번째

 

 

 

계단 오르기 문제와 거의 비슷한데, 계단 오르기는 N번째 계단을 항상 밟아야 했지만 이 문제는 N번째 포도주를 꼭 마시지 않아도 된다는 차이가 있다.

dp[k]를 k번째 포도주까지 지나쳤을 때(마셨을 때가 아니다!) 최대값이라고 하자. 계단 오르기 문제처럼 dp[k-3]+v[k-1]+v[k], dp[k-2]+v[k] 중 큰 값이 정답 후보인 것은 맞지만 k번째 포도주를 마시지 않아도 되므로 dp[k-1] 또한 정답 후보가 될 수 있다. 세 값 중 가장 큰 값을 저장하면 된다.

사실 최대값을 구한다는 측면에서 dp[k-1]을 굳이 고려하지 않고 구한 뒤 dp[n], dp[n-1], ...을 탐색하여 최댓값을 구해도 정답은 나올 수 있다. 하지만 dp[k-1]까지 고려하는 것이 정석에 가깝다.

 

 

 

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

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<int> v(n+1), dp(n+1);
  
  for(int i=1;i<=n;i++)  cin >> v[i];
  
  dp[1]= v[1];
  if(n>=2)  dp[2]= v[1]+v[2];
  
  for(int i=3;i<=n;i++)  dp[i]= max(dp[i-1], (max(dp[i-3]+v[i-1], dp[i-2]) + v[i]));
  
  cout << dp[n];
  
  return 0;
}