[백준/C언어] 2156번 - 포도주 시식

백준 웹사이트 "2156번 - 포도주 시식" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

2156번: 포도주 시식

---

소스 코드

#include <stdio.h>

int max(int a, int b, int c);

int main(void){
    int n;
    scanf("%d", &n);

    int wine[n+1];
    for(int i=1; i<n+1; i++){
        scanf("%d", &wine[i]);
    }

    int quantity[n+1];
    //quantity[i]: i 번째 잔까지, 마실 수 있는 최대 양
    quantity[0] = 0;
    quantity[1] = wine[1];
    //printf("%d: %d\n", 1, quantity[1]);
    if(n>=2){
        quantity[2] = wine[1]+wine[2];
        //printf("%d: %d\n", 2, quantity[2]);
    }
    for(int j=3; j<n+1; j++){
        quantity[j] = max(quantity[j-2]+wine[j], quantity[j-3]+wine[j-1]+wine[j], quantity[j-1]);
        //printf("%d: %d\n", j, quantity[j]);
    }

    printf("%d\n", quantity[n]);
}

int max(int a, int b, int c){
    if(a>b && a>c)
        return a;
    else if(b>c)
        return b;
    else
        return c;
}

---

문제 풀이

  'wine[n+1]'은 각 포도주 잔에 들어있는 포도주의 양입니다. (wine[i] : i 번째 잔의 포도주 양)

  'quantity[n+1]'은 각 잔까지 마실 수 있는 최대 양입니다. (quantity[i]: i 번째 잔까지 마실 수 있는 최대 양)

  세 잔을 연속해서 마실 수 없기 때문에, j≥3일 때 다음과 같은 관계식이 성립합니다.

$$ quantity[j] = $$

$$ max(quantity[j-2]+wine[j], quantity[j-3]+wine[j-1]+wine[j], quantity[j-1]) $$

이때 quantity[j-2] + wine[j]는 j-1번째 잔을 마시지 않았을 경우, quantity[j-3]+wine[j-1]+wine[j]는 j-2번째 잔을 마시지 않았을 경우이겠죠? 마지막 quantity[j-1]는 앞선 경우들만큼 직관적이지 않은데, quantity[j]는 j번째 잔까지 마실 수 있는 최대 양이므로 j번째 잔을 꼭 마시지 않아도 됩니다. 즉, j번째 잔을 마시지 않고 j-1번째, j-2번째 잔을 마셔야 더 많은 양을 마시게 되는 경우도 있기 때문에 이런 경우까지 고려해줍니다. 아래 추가 예제가 그런 경우인데, 제출하기 전에 아래 입력도 시험해보면 좋습니다.

  동적 계획법을 완료하면, 마지막 quantity[n]을 출력하여 최대로 마실 수 있는 포도주의 양을 구할 수 있습니다.

---

추가 예제

입력

10
0
0
10
0
5
10
0
0
1
10

 

출력

36