[BOJ 2156] 포도주 시식

2156번: 포도주 시식

 

1. 문제 설명

 

2. 구현 아이디어 1 - 맞았습니다 !!

연속으로 3잔을 모두 마실 수 없다는 점을 유의해서 풀면 되는 문제이다.

 

이제까지 마신 최대 포도주의 양을 계산하고, 연속으로 마신 잔의 수에 따라 현재 위치에 있는 포도주를 마실지 말지 결정하는 것이 DP 문제에서 나오는 자주 나오는 로직이여서 DP를 사용하여 문제를 풀 수 있다고 생각할 수 있었다.

 

각 위치의 포도주의 양을 담은 배열을 arr라고 하고 dp[i] = 0~i번째 위치에 있는 포도주까지 고려했을 때 마신 포도주의 양의 최댓값이라고 했을 때, 3잔을 연속으로 마시지 않으려면 아래와 같은 선택지가 있다.

1. 현재 위치에 있는 포도주를 마시지 않는다 → dp[i] = dp[i-1]
2. 2번째 전 위치까지 마실 수 있는 최대를 마시고, 이번 포도주를 마신다. → dp[i] = dp[i-2] + arr[i]
   • 마지막 3개의 포도주를 i-2, i-1, i번째 포도주라고 할 때, i-1번째 포도주를 마시지 않는 선택지이다.
3. 3번째 전 위치까지 마실 수 있는 최대를 마시고, 1번째 전 위치의 포도주와 이번 포도주를 마신다. → dp[i] = dp[i-3] + arr[i-1] + arr[i]
   • 마지막 3개의 포도주를 i-2, i-1, i번째 포도주라고 할 때, i-2를 마시지 않는 선택지이다.

 

이제 반복문을 돌면서 DP 배열을 채울 때 위의 3가지 선택지 중 가장 큰 값을 선택하면 된다.

C++에서 max 함수를 사용할 때 인자가 3개 이상이라면 { }로 감싸주어야 한다.

🍥 점화식
dp[i] = max({dp[i-1], dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]});

 

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    vector<int> arr = vector<int>(n);
    vector<int> dp = vector<int>(n);

    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    dp[0] = arr[0];
    dp[1] = arr[0] + arr[1];
    dp[2] = max(dp[1], max(dp[0] + arr[2], arr[1] + arr[2]));

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

    cout << dp[n-1] << "\n";
}

 

이제까지 DP 문제를 풀 때 대부분 2가지 경우를 비교하는 방식을 사용했기 때문에 처음에는 3가지 경우를 비교해야 한다는 것이 잘 떠오르지 않았다.

비교해야 될 경우가 많아져도 당황하지 말고 문제를 풀자!