BOJ 16193 - 차이를 최대로 2

BOJ 16193 - 차이를 최대로 2

그냥 덱으로 대충 풀다가 맞아버렸는데, 좀 더 수학적으로 생각을 해볼 예정이다.

• 수들을 정렬하고 가장 작은수나 가장 큰 수를 처음에 사용한다 해보자.
• 다른 수들을 붙일 수 있는 경우의 수 네 가지를 확인한다. 남은 수 중 가장 작은것이나 가장 큰것 2개 를 왼쪽에 붙이거나 오른쪽에 붙이거나 총 4가지 중 가장 크기가 큰 행동대로 시행한다.

void solve() {
   int n;
   cin >> n;
   deque<int> a(n), ans;
   fv(a);
   sort(all(a));
   ans.pb(a.back());
   a.pop_back();
   int sum = 0;
   while (sz(a)) {
      int LL = abs(a.front() - ans.front());
      int LR = abs(a.front() - ans.back());
      int RL = abs(a.back() - ans.front());
      int RR = abs(a.back() - ans.back());
      if (LL >= LR && LL >= RL && LL >= RR) {
         ans.push_front(a.front());
         a.pop_front();
      } else if (LR >= LL && LR >= RL && LR >= RR) {
         ans.push_back(a.front());
         a.pop_front();
      } else if (RL >= LL && RL >= LR && RL >= RR) {
         ans.push_front(a.back());
         a.pop_back();
      } else {
         ans.push_back(a.back());
         a.pop_back();
      }
   }
   for (int i = 0; i < n - 1; i++) sum += abs(ans[i] - ans[i + 1]);
   cout << sum;
}