Algorithm/Algorithm 문제 풀이

[BAE/<JOON> 문제풀이] 2156. 포도주 시식 (DP.008)

폭풍저그머성찡 2020. 4. 20. 21:52

https://www.acmicpc.net/problem/2156

 

2156번: 포도주 시식

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고

www.acmicpc.net

저번의 계단문제와 비슷한 문제다.

 

구현도 거의 비슷하게 했는데 한가지 다른 점이 계단 문제에서는 무조건 2칸안의 계단을 밟아야만 했지만

 

포도주 문제는 원하는 만큼의 노드를 건너 뛸 수 있다는 점이었다. 

 

그리고 모르고 최댓값 구하는 코드를 for문 안에 넣어서 돌렸더니 1이 입력됬을 때 최댓값 갱신이 안되서 오답이 나오더라.

 

사실 코딩 자체는 10분 안에 끝났는데 이거를 2시간 동안 찾았다.

 

경험치가 부족하다..

 

더보기 
#include <iostream>
#include <vector>

using namespace std;

struct jan {
    int prev, nprev; 
    //nprev : 이전 잔 미포함 최댓값
    //prev : 이전 잔 포함 최댓값
};

int max(int x, int y) {
    return (x > y ? x : y);
}

int main()
{
    int n;
    cin >> n;
    vector<int> arr;
    vector<jan> dp;
    arr.resize(n + 1);
    dp.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    dp[0] = { 0, 0 };
    dp[1] = { arr[1], arr[1] };
    int mx = 0;
    for (int i = 2; i <= n; i++) {
        int p = dp[i - 1].nprev + arr[i];//이전 와인잔의 전잔을 안마신 최댓값 + 현재 와인잔의 값
        int np = 0;
        for (int j = i - 2; j >= 1; j--) {
            if (np < max(dp[j].prev, dp[j].nprev)) np = max(dp[j].prev, dp[j].nprev); //혹은 -2번째 와인잔부터 그 이전의 최댓값중 최댓값
        }        
        np += arr[i];
        
        dp[i].prev = p;
        dp[i].nprev = np;        
    }

    for (int i = 1; i <= n; i++) {
        //cout << dp[i].prev << " " << dp[i].nprev << endl;
        if (mx < max(dp[i].prev, dp[i].nprev)) mx = max(dp[i].prev, dp[i].nprev);
    }

    cout << mx << endl;
    return 0;
}

 

이 문제와 계단 문제의 차별점은 i for문안에 있는 j for문이다. 단순이 -2부분에서 계산하는것이 아니라

 

이전 와인잔의 최댓값을 모두 계산하여 현재 와인잔의 이전 와인잔 미포함 최댓값을 구한다.