백준 10819번 차이를 최대로 (C++)

문제 링크 : www.acmicpc.net/problem/10819

10819번: 차이를 최대로

next_permutation STL이 있다는 것을 모른다면 브루트 포스 알고리즘을 활용한 백 트래킹을 구현해야 했을 것이다.

순열을 자동으로 구해주는 next_permutation 덕분에 고민하지않고 쉽게 풀 수 있었다.

 

#include <iostream>
#include <algorithm>
#include <cmath>
#define MAX 10000
using namespace std;

int arr[MAX], ans = -1e4;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0, cnt = 0;
    cin >> n;
    for(int i=0; i<n; i++) cin >> arr[i];
    sort(arr,arr+n);
    do{
        int temp = 0;
        for(int i=1; i<n; i++) temp += abs(arr[i]-arr[i-1]);
        if(ans<temp) ans = temp;
    }while(next_permutation(arr,arr+n));
    cout << ans << "\n";
    return 0;
}