문제

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
int factorial(int num)
{
    if (num <= 1) return 1;
    return num * factorial(num - 1);
}
bool next_permutation(vector<int> &arr,int n)
{
  int i = n-1;
  while(i>=0 && arr[i]<= arr[i-1])
  {
    i-=1;
  }
  if(i<=0){
    return false;
  }
  int j = n-1;
  while(arr[j]<=arr[i-1])
  {
    j-=1;
  }
  swap(arr[i-1],arr[j]);
  sort(arr.begin()+i,arr.end());
  return true;
}
int calculate(vector<int> &arr,int n)
{
  int sum=0;
  for(int i=0;i<n-1;i++)
  {
    sum+= abs(arr[i] - arr[i+1]);
  }
  return sum;
}
int main()
{
  int n;
  cin>>n;
  vector<int> arr(n);
  for(int i=0;i<n;i++)
  {
    cin>>arr[i];
  }
  sort(arr.begin(),arr.end());
  int f=factorial(n);
  int temp;
  int min = calculate(arr,n);
  while(1)
  {
    if(f==0)
      {
        break;
      }
      if(next_permutation(arr,n))
      {
        temp=calculate(arr,n);
        if(temp>min)
        {
          min=temp;
        }
      }
      f-=1;
  }
  cout<<min;
}

풀이

BOJ 10972 다음순열 문제를 응용하여 풀었다.

모든 순열의 계산값을 구하기위해 n! 만큼 반복해 주었고, 한번 반복할때마다 최대값을 비교해주었다.

다음순열문제와 다른점은 처음에 주어진 순열을 sort 하고 시작해야했다.