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

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

2156번: 포도주 시식

문제는 3연속 연결되어 있는 포도주를 마실수 없다는 것이다.

따라서 가능한 경우를 생각해보면 현재 위치를 i라고 했을 때

1. 앞 최댓값(dp[i-1])을 그대로 가져가는 경우

2. 앞앞 위치의 최댓값에 현재 포도주를 더하는 경우(dp[i-2] + wine[i])

3. 앞앞앞 위치의 최댓값에 이전 포도주와 현재 포도주를 더하는 경우(dp[i-3] + wine[i-1] + wine[i])

위의 세가지 경우로 나눌 수 있다.

따라서 i-3까지 등장하기 때문에 인덱스 오류가 나지 않도록 dp[0],dp[1],dp[2]까지는 미리 구해주어야한다.

실제로 위의 3개는 규칙에 맞지도 않는다.

그래서 앞의 3개만 구해주고 구한 점화식에 따라서 나머지 dp벡터를 완성해주면 된다.

 

코드는 다음과 같다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;
int main(){
  ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
  int n;
  cin >> n;
  vector<int> wine(n);
  vector<int> dp(n);
  for(int i = 0; i < n; i++){
    cin >> wine[i];
  }
  dp[0] = wine[0];
  dp[1] = wine[0] + wine[1];
  dp[2] = max({dp[1], dp[0]+wine[2], wine[1]+wine[2]});
  for(int i = 3; i < n; i++){
    dp[i] = max({dp[i-1], dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i]});
  }
  cout << *max_element(dp.begin(), dp.end());
}

 

 

 

Dp 문제로  Dp를 많이 접해보지 않았으면, 꽤 시간이 걸릴만한 문제라고 생각한다.

본인은 다행이 최근 Dp를 공부하고 있기도 하고 비슷한 유형을 Class3 에서 접해서 풀어낼 수 있었다.

Dp도 이제 막 시작해서 바로 쓱쓱 코드를 짜진 못했고, 연필로 예제입력을 써보면서 점화식을 찾았다.

그래도 한번의 연필질로 바로 점화식을 찾아서 기분이 좋았다(?).