[BOJ/C++] 2156: 포도주 시식

🥈 Silver 1

✏️ 1차 솔루션

⭐️ DP 로 풀이
각 DP 값에는 현재 잔을 최종적으로 마실 경우 최대값을 저장
0번째 잔 최대값(dp[0]): 무조건 마심
1번째 잔 최대값(dp[1]): 0번째 잔도 마심
2번째 잔 최대값(dp[2]): 0번째 잔, 1번째 잔 중에 더 큰 잔 마심
3번째 잔 ~ n 번째 잔
➡️ (i-1) 번째 잔 + (i-3) 번째 dp 값, (i-2) 번째 잔 중에 더 큰 잔 마심

🚨 1차 trouble

테케는 통과하지만 히든테케는 통과하지 못함..

✏️ 최종 솔루션

dp 에는 첫번재 잔부터 n 번재 잔까지 주어졌을 때 먹을 수 있는 최대값을 저장
3 ~ n번째 dp 에 대해서

1. i-1 번째 마시고 i 번째는 안 마심 ➡️ dp[i-1]
2. i-2 번째 마시고 i 번째 마심 ➡️ dp[i-2] + i 번째 잔
3. i-3 번째 마시고 i-1 번째 마시고 i 번째 마심 ➡️ dp[i-3] + dp[i-1] + i 번째 잔

📌 self feedback

dp 값의 전제를 잘못 설정함
현재 잔을 마시는 경우에서 현재 잔을 마시면 연속 잔이 되는 경우와 연속 잔이 되지 않는 경우를 모두 고려했어야하는데 연속 잔이 되는 경우만 고려함
i 번째 잔을 마시는 경우와 마시지 않는 경우를 나눠서 고려했어야 함

✏️ 최종 code

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

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