본문 바로가기

Programming/BOJ

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])




참고



태그