백준 10819번 C++ 순열 활용 문제

차이를 최대로

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

next_permutation?

이 문제의 최대 배열 크기는 고작 8....

그냥 모든 경우를 다 세어도 문제 없는 문제이다

그런 함수가 뭔지 모르겠어서 검색했더니 next_permutation을 쓰란다

https://twpower.github.io/82-next_permutation-and-prev_permutation 참고

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//next_permutation을 이용해서 푸는 문제
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie();
    int N;
    cin>>N;
    vector<int> arr(N);
    for(int i=0; i<N; i++)
        cin>>arr[i];
 
    sort(arr.begin(), arr.end());
    int sum=0;
    do{
        int tmp=0;
        for(int i=1; i<N; i++)
            tmp+=abs(arr[i-1]-arr[i]);
        sum=max(sum, tmp);
    }while(next_permutation(arr.begin(), arr.end()));
    //bool값 반환하는 함수
 
    cout<<sum<<endl;
    return 0;
}