[2156] 포도주 시식 - C++

몇 주 전에 답을 보고 풀었던 문제를 글을 쓰기 위해 다시 풀어 보았다.

어떻게 풀어야 할지는 기억이 나지 않는 상태에서 풀었다.

---

문제에 접근하는 방식

포도주잔에 들어있는 숫자들을 나열해 보았다.

조건이 있다면 3잔 연속으로 먹으면 안 된다는 것! (아래 사진 참고)

불가능

어떻게 해야 조건을 다 맞추며 해결할 수 있을까? 를 고민했다.

 

• $DP [1] = wine [1]$
• $DP [2] = wine [1] + wine [2]$

로 채워 줬는데, 그 이유는 어차피 2번째 와인을 맛보는 순서까지 왔을 때의 최대는 저것뿐이기 때문

 

이제 3번째부터가 문제의 문제의 문제인데, 뭐가 문제인지 살펴보자.

이렇게 되면 3잔 연속이 되어 버린다, 그렇기에 한 가지 방법이 있다.

 

1 번째 경우

세잔 연속이 아니다!

이렇게 DP [i-2] 번째 잔까지의 최대를 선택하면 연속이 아니게 된다.

 

2 번째 경우

우리는 현재 와인잔을 마시기 바로 이전에 한번 마셨다는 가정을 하고, DP [i-3] 번째 잔까지의 최대와의 합

 

3번째 경우

하나가 더 있어서 놀랄 수 있다.

위 두 가지 경우만 비교하다 보면 최대를 찾기가 어렵다, 그렇기 때문에 한 가지 장치를 해둬야 한다.

 

가정을 해보자 만약 현재 요소가 뒤의 요소보다 작은 상황이 나왔다.

27 보다 9가 더 작다

이때 그냥 둔다면 나중에 저 요소를 사용할 때 최대의 가치를 낼 수 없게 된다.

n-1까지의 값을 최댓값으로 둘 수 있다. 굳이 n을 포함시킬 필요가 없기 때문이다.

 

점화식

$$dp[i] = max(wine [i] + dp [i-2], wine [i]+wine [i-1]+dp [i-3], dp [i-1])$$

 

코드

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
int n, arr[10002];
long long int dp[10002];

int main(){
  init();
  cin >> n;
  for(int i= 1; i <= n; ++i)
    cin >> arr[i];
  dp[1] = arr[1], dp[2] = dp[1]+arr[2];
  for(int i = 3; i <= n; ++i)
    dp[i] = max({arr[i] + dp[i-2], arr[i]+arr[i-1]+dp[i-3], dp[i-1]});
  cout << dp[n];
  return 0;
}

 

글을 마치며

여전히 DP문제는 어렵다, 식을 생각하는 것 자체가 힘들다.

그때는 답을 보고 풀었던 문제 이더라도 20일이 지난 오늘, 이렇게 다시 풀었을 때 풀어낸 내가 자랑 스럽다.

칭찬한다.