(28039) 카드 게임 2

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

 

 

 

실제로 백준에서 푼 문제는 많지만, 그 많은 코드를 다 가져와서 다시 정리하는 것은 너무 힘들고 불필요하다고 생각해서 단계별로 풀어보기만 가져왔다. 하지만 난이도가 높은 문제는 그냥 묻히도록 두기 조금 아깝다는 생각에, 단계별로 풀어보기 문제가 아니면서 솔브닥 기준 다이아 티어 문제였던 3개의 문제만 가져왔다. 이건 그 중에서도 다이아4로 가장 높은 난이도의 문제였다.

DP 2 단계에서 풀었던 문제의 제한 조건이 커진 문제다.

만약 a,b,c 순서대로 세 카드가 놓여 있고 b>max(a,c)라고 하자. 내가 a와 c 중 무엇을 가져가든 상대방은 당연히 b를 가져갈 것이고, 나는 남은 것을 가져가므로 나는 a와 c, 상대방은 b를 가져가게 된다. 따라서 이 세 숫자가 영향을 끼친 점수 차이는 a+c-b가 되고, 세 숫자를 a+c-b 하나로 압축해도 게임의 결과는 동일하게 유지된다. 스택을 이용해 a≤b≥c 같은 산 모양이 나올 때마다 이를 압축하면 마지막에는 중간에 최소값이 있고 양 끝으로 갈수록 커지는 V자 모양의 수열만 남게 될 것이다. 이 경우 어차피 안쪽의 숫자는 항상 더 작으므로 양끝 숫자 중 더 큰 것을 가져가는 게 이득이고, 투 포인터로 그리디하게 더 큰 것을 가져가는 전략을 구현하면 결과를 구할 수 있다. 이때 주의할 점은 이 결과는 절대적 점수가 아닌 상대적인 점수 차이이므로, 절대적인 점수(처음 카드의 총합)에서 상대적인 점수를 더하고 뺀 뒤 2로 나눠줘야 두 사람이 실제로 갖는 점수가 나온다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

long sol(){
  int n;
  cin >> n;
  
  long sum= 0;
  vector<int> v(n);
  for(int i=0;i<n;i++){
    cin >> v[i];
    sum+=v[i];  
  }
  
  vector<long> compress;
  
  for(int i=0;i<n;i++){
    compress.push_back(v[i]);
    
    while(true){
      int sz= compress.size();
      
      if(sz>=3 && (compress[sz-3]<=compress[sz-2] && compress[sz-2]>=compress[sz-1])){
        long tmp= compress[sz-3]+compress[sz-1]-compress[sz-2];
        
        compress.pop_back();
        compress.pop_back();
        compress.pop_back();
        compress.push_back(tmp);
      }else{
        break;
      }
    }
  }
  
  int l=0, r=compress.size()-1, turn=1;
  long diff=0;
  
  while(l<=r){
    if(compress[l]>compress[r]){
      diff+= compress[l]*turn;
      l++;
      turn*=-1;
    }else{
      diff+= compress[r]*turn;
      r--;
      turn*=-1;
    }
  }
  
  return (sum+diff)/2;
}

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
    
  cin >> T;
    
  while(T--){
    cout << sol() << "\n";
  }
    
  return 0;
}