[C++] 백준 온라인 저지 2156번 포도주 시식 풀이

일정한 규칙에 따라 잔에 담긴 포도주를 마실 때 마실 수 있는 최대값을 구하는 문제

 

---

문제의 조건

 

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

 

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

 

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

 

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

 

 

풀이 과정

 

 정답률 보고 못 풀 것이라 생각했지만(아직 40%대 까지만 가넝한...) 아직 DP를 잘 못 해서 참 어려웠던 문제입니다 ㅠ.ㅠ 

 

https://yabmoons.tistory.com/512

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

 

 풀이에 굉장히 도움이 된 블로그. 설명이 정말정말 자세해서 좋아요. 

 

 복습 차원에서 이 문제의 풀이 과정을 적어보자면, 마실 수 있는 와인의 최대양을 구하는데

 

1. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

라는 조건이 있습니다. 그러면 첫번째 와인과 두번째 와인을 마실 때 까지는 그냥 먹으면 되니까 별 문제가 없는데 세번째 와인잔부터는 저 조건을 고려해야 합니다. 

 즉, 세번째 와인을 마시는 순간부터는 

 

 

 위 그림처럼 1, 2번 와인을 마시고 3번 와인을 마시지 않는 경우

 1번과 3번 와인을 마시는 경우

 2번과 3번 와인을 마시는 경우가 생깁니다. 

 그런데 여기서 단순하게 두 잔의 합만 보면 2번과 3번 와인을 합친 것이 5로 가장 크지만 4번째 와인잔에 가게 되었을 때 3번째 와인을 마시지 않고 1번과 2번 와인을 마시고 4번 와인을 마시는 것이 더 클 수도 있습니다. 그렇기 때문에 세번째 와인을 마시게 되는 순간부터는 네번째 와인의 양을 고려해서 1~3번 와인들 중 몇 번째 와인까지 마실 것인지 결정해야 합니다. 

 

 

 그림으로 한 번 더 정리해보면 위와 같은 경우들을 생각해 볼 수 있습니다. 

 여기에서 우리는 3번 와인을 마시는 경우와 마시지 않는 경우로 나눠서 생각해 볼 수 있습니다. 

 3번 와인을 마시는 경우에는 1번 + 3번 와인

 2번 + 3번 와인

 3번 + 4번 와인을 마실 수 있습니다. 

 

 3번 와인을 마시지 않는다면 1번 + 2번 + 4번 와인

 2번 + 4번 와인

 4번 와인

 아무것도 마시지 않은 경우로 나눌 수 있습니다. 여기서 맨 마지막 아무것도 마시지 않는 경우는 누가 봐도 최대양이 될 수 없기 때문에 제외할 수 있습니다. 

 

 지금까지 도출한 아이디어를 와인잔의 갯수를 n개로 늘려서 적용해 봅시다. n번째 와인잔까지 마신 와인의 최대양을 x라고 가정해 봅시다. n번째 와인잔까지 마신 와인의 최대양을 배열에 저장한다면 arr[n] = x 라고 할 수 있습니다. 

 

 

 n번째 와인잔에 왔을 때 n번째 와인을 마실 수 있는 경우는 앞에서 연속해서 2잔 이상 마시지 않았을 때 입니다. 즉 n-3번과 n-2번째 와인까지 쭉 마셔왔다면 n-1번째 와인은 건너뛰어야 n번째 와인을 마실 수 있습니다. 아니면 n-3번째 와인까지 마셔오다가(n-4번째 와인을 마시고 n-3번째 와인을 마셨을 수도 있고 n-3번째 와인만 마셨을 수도 있습니다) n-2번째 와인을 건너뛰면 n-1번과 n번째 와인을 연속해서 마실 수 있습니다. 

 아니면 n-1번째 와인까지 쭉 마셔왔기 때문에 n번째 와인은 마시지 못 할 수도 있습니다. 이 경우에는 n-2번째 와인과 n-1번째 와인을 연속해서 마셨고 n-4, n-5번째를 연속해서 마시고 ... 를 반복했을 수 있습니다. 

 

 이렇게 n번째 와인잔에 왔을 때 가정할 수 있는 지금까지 마신 와인의 양은 위 세 가지 경우 중 하나이고, 문제의 답은 최대양을 구하는 것이기 때문에 이 세 가지 경우 중 최대양을 구하면 됩니다. 

 

arr[n] = max(arr[n-3] + wines[n-1] + wines[n], arr[n-2] + wines[n], arr[n-1]);

 

 그렇다면 위와 같은 점화식을 세울 수 있습니다. 이제 이것을 반복문을 돌려서 DP 배열에 저장한 후 DP 배열의 가장 마지막 인덱스값을 출력하면 됩니다. algorithm의 max 함수는 두 가지 값만 비교할 수 있기 때문에 3개 이상을 비교할 땐 컨테이너에 넣어서 비교하거나 나눠서 비교하거나 여러 방법이 있겠지만 저는 우선순위 큐로 최대힙을 만들어서 사용했습니다. 

 

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main()
{
    unsigned n;
    cin >> n;
    
    vector<unsigned> wines(n + 1, 0);
    for (int i = 1; n >= i; i++)
        cin >> wines[i];
    
    vector<unsigned> DP(n + 1, 0);
    DP[1] = wines[1];//첫번째 와인을 마실 때
    DP[2] = wines[1] + wines[2]; //두번째 와인을 마실 때
    for (int i = 3; wines.size() > i; i++)
    {
        //큰 순서대로 자동 내림차순 정렬 되도록 최대힙 선언 
        priority_queue<unsigned> heap;
        heap.emplace(DP[i-3] + wines[i-1] + wines[i]);
        heap.emplace(DP[i-2] + wines[i]);
        heap.emplace(DP[i-1]);
        
        DP[i] = heap.top();
    }
    
    cout << DP.back();
    
    return 0;
}

 

 당분간 와인은 피하고 싶어졌어...