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

2156번: 포도주 시식

조건들을 생각해야 했던 dp 문제이다. 최대로 마실 수 있는 포도주 양을 출력하되 3잔을 연속으로 마실 수 없는 조건이 있다. 여기서 dp는 dp[n] = n번째 잔을 마실 때 최대 양이다. dp를 처음부터 채워나가보면 아래와 같다.

• n = 1 일 경우, dp[1] = wine[1]
• n = 2 일 경우, dp[2] = wine[1] + wine[2]
• n = 3 일 경우, dp[3] = max({ wine[1] + wine[2], wine[1] + wine[3], wine[2] + wine[3] })

n이 3일 경우를 보면 세가지의 조건 중 최댓값이 dp[3]에 들어가게 된다. 이를 점화식으로 나타내면 dp[n] = max({ dp[n - 1], dp[n - 2] + wine[n], dp[n - 3] + wine[n - 1] + wine[n] })과 같다. 반복문을 돌면서 점화식에 따라 dp를 채우고 dp[n]을 출력해 주었다. dp를 생각할 때는 1부터 n까지 채워가는 방식에 집중해야겠다.

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int wine[10001];
int dp[10001];

void solution() {
    dp[1] = wine[1];
    dp[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 << dp[n];
}

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

    cin >> n;

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

    solution();

    return 0;
}