[BOJ] 2156_포도주 시식

포도주 시식

문제 링크: https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

dp[n]: n번째 와인을 마셨을 때 최댓값이라고 정의하자.
dp[n].first: n번째 와인을 마실 때, n-1번째 와인도 마셨을 때
dp[n].second: n번째 와인을 마실 때, n-1번째가 아닌 와인을 마셨을 때
로 하여 따로 저장한다.

또한 최대값을 저장하기 위해 첫번째 인덱스와 두번재 인덱스를 저장할 pair를 선언한다.
first와 second는 전체 와인마실때 최대값들이며, 인덱스가 더 높은 순서대로 정렬된다.

 

최대값 pair의 first가 dp[n-1]번째의 바로 직전일 경우 dp[n].first에 무조건 최대값 pair의 두번째 인덱스인 second를 더한다.
그리고 dp[n].second에서는 최대값 pair의 first가 아닌 second의 값을 넣되, 가장 큰 값을 더해준다.

 

최대값 pair의 first가 dp[n-1]번째의 바로 직전이 아닌 경우 first와 second 모두 비교하여 가장 큰 값만 더해준다.

 

• 정답코드

    #include<iostream>
    #include<algorithm>
    using namespace std;
  
    #define maxNum 10001
    #define max(a, b) (a > b ? a : b)
  
    int juice[maxNum];
    pair<int, int> dp[maxNum];
    int maxidx = 0;
    pair<int, int> maxList;
    // frist는 현재 가장 최대 값
    // second는 first를 지정할 때 바로 직전 값일 경우 두번째로 큰 값
    int n;
  
    pair<int, int> sorting[3];
    bool compare(pair<int, int>& a, pair<int, int>& b) {
        if (a.first == b.first)
            return a.second < b.second;
        return a.first > b.first;
    }
  
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL); cout.tie(NULL);
  
        cin >> n;
  
        for (int i = 1; i <= n; i++) {
            cin >> juice[i];
        }
  
        dp[1].first = juice[1];
        dp[1].second = juice[1];
        maxList.first = 1;
        maxList.second = 1;
  
        dp[2].first = juice[2] + juice[1];
        dp[2].second = juice[2];
  
        int temps = max(dp[2].first, dp[2].second);
  
        if (temps > juice[1]) {
            maxList.first = 2;
            maxList.second = 1;
        }
      for (int i = 3; i <= n; i++) {
          if (maxList.first == i - 1) {
              // 현재 최대 값이 바로 직전이라면
              dp[i].second = max(dp[maxList.second].second, dp[maxList.second].first) + juice[i];
              dp[i].first = dp[maxList.first].second + juice[i];//직전합
          }
          else {
              // 현재 최대 값이 직전게 아니라면
              int temp1 = max(dp[maxList.first].second, dp[maxList.first].first);
              int temp2 = max(dp[maxList.second].second, dp[maxList.second].first);
  
              dp[i].second = max(temp1, temp2) + juice[i]; //직전이 아닌 합
              dp[i].first = max(temp1, temp2) + juice[i]; //직전합
          }
          // 큰 값 순서대로 정렬하고 두 개를 추출 후 인덱스 더 높은 순으로 재정렬 first, second 입력
          sorting[0].first = max(dp[maxList.first].second, dp[maxList.first].first);
          sorting[0].second = maxList.first;
  
          sorting[1].first = max(dp[maxList.second].second, dp[maxList.second].first);
          sorting[1].second = maxList.second;
  
          sorting[2].first = max(dp[i].second, dp[i].first);
          sorting[2].second = i;
  
          sort(sorting, sorting + 3, compare);
  
          maxList.first = (sorting[0].second > sorting[1].second ? sorting[0].second : sorting[1].second);
          maxList.second = (sorting[0].second < sorting[1].second ? sorting[0].second : sorting[1].second);
      }
  
      int temp1 = max(dp[maxList.first].second, dp[maxList.first].first);
      int temp2 = max(dp[maxList.second].second, dp[maxList.second].first);
  
      cout << max(temp1, temp2);
  
      return 0;
  }