[BOJ] 2156: 포도주 시식

문제 링크

설명

dp[i]는 i번 것까지 먹었을 때 최댓값.

현재 상태 i번째라고 했을 때 점화식 3개

1. 현재 것을 먹지 않았을 때 -> dp[i] = dp[i - 1] // i - 1 번째까지 마셨던 것을 업데이트
2. 이번 것만 먹을 때(1연속) -> dp[i] = glasses[i] + dp[i - 2] // i - 1 번은 분명히 마시지 않는다.
3. i, i - 1번을 먹을 때(2연속) -> dp[i] = glasses[i] + glasses[i - 1] + dp[i - 3] // i - 2 번은 분명히 마시지 않는다.

코드

#include <cstdio>
const int mn = 10001;
inline int max(int a, int b) {
    return a > b ? a : b;
}
 
inline int max(int a, int b, int c) {
    int res = max(max(a, b), c);
    return res;
}
 
int main()
{
    int n, p[mn], dp[mn];
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &p[i]);
    
    /*
    조건: 3연속으로 마실 수 없음.
    dp[i]: i번째에서 마실 수 있는 포도주의 최대량
    현재 상태 i
    1. 마시지 않았을 때 -> dp[i] = dp[i - 1];
    2. 1연속으로 마실 때 -> dp[i] = p[i] + dp[i - 2]; // i - 1은 마시지 않는다.
    3. 2연속으로 마실 때 -> dp[i] = p[i] + p[i - 1] + dp[i - 3]; // i - 2번째는 마시지 않는다.
    */
    dp[0] = 0;
    dp[1] = p[1];
    dp[2] = p[2] + p[1];
    for (int i = 3; i <= n; ++i) {
        dp[i] = max(dp[i - 1], p[i] + dp[i - 2], p[i] + p[i - 1] + dp[i - 3]);
    }
    printf("%d\n", dp[n]);
    return 0;
}