BOJ 2156 · 포도주 시식

알고리즘 분류 : 다이나믹 프로그래밍  

N개의 포도주 잔이 있을 때, 최대로 마실 수 있는 포도주의 양을 구해야 한다. DP를 이용하여 포도주 마시는 규칙에 따라 구현하면 된다.

• 포도주는 연속으로 3잔 이상 마실 수 없다. 즉, 연속하여 마실 수 있는 포도주는 최대 2잔이다.
• D[N] : N 번째 잔의 포도주를 마셨을 때, 최대로 마실 수 있는 포도주의 양

• D[N]은 3가지 경우의 수로 나눌 수 있으며, 3가지 값 중 가장 큰 값이 D[N]이 된다.
• 1. N 번째 잔을 마시지 않은 경우 : D[N-1]
• 2. N 번째 잔이 연속 1잔째 마신 경우 : D[N-2] + P[N] (N-1 번째 잔은 마시지 않아야 한다.)
• 3. N 번째 잔이 연속 2잔째 마신 경우 : D[N-3] + P[N-1] + P[N-1] (N-2 번째 잔은 마시지 않아야 한다.)

---

C++ 소스코드

#include <cstdio>
#include <algorithm>
using namespace std;

int n, d[10001], p[10001];

void solve() {
    d[1] = p[1], d[2] = p[1]+p[2];
    for (int i=3; i<=n; i++) {
        d[i] = d[i-1];
        d[i] = max(d[i], d[i-2]+p[i]);
        d[i] = max(d[i], d[i-3]+p[i-1]+p[i]);
    }
    printf("%d\n", d[n]);
}

int main() {
    scanf("%d", &n);
    for (int i=1; i<=n; i++) scanf("%d", &p[i]);
    solve();
    return 0;
}

---

Python 3 소스코드

def solve():
    d[1], d[2] = p[1], p[1]+p[2]
    for i in range(3, n+1):
        d[i] = d[i-1]
        d[i] = max(d[i], d[i-2]+p[i])
        d[i] = max(d[i], d[i-3]+p[i-1]+p[i])

n = int(input())
d = [0]*(n+2)
p = [0]+[int(input()) for _ in range(n)]+[0]
solve()
print(d[n])

---

참고

• 백준 온라인 저지 : BOJ 2156