백준 10819 차이를 최대로

abs함수와 max함수를 쓴다는 것 외에는 딱히 설명할게 없다.

한 가지 중요한 점은 순열을 사용하기 위해서는 먼저 정렬을 해야 한다는 것이다.(모든 경우를 다 돌려보기 위해서)

next_permutation을 사용할 때는 첫 번째 순열을 돌린 후에 해야 하기 때문에 do-while을 사용하자.

시간복잡도는 N이 최대 8이므로 8!로 순열로 해결할 수 있는 문제임을 알 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(int argc, char* argv[]) {
    int n, ans = 0, sum;
    cin >> n;
    int *bf = new int[n];
    for (int i = 0; i < n; i++) cin >> bf[i];
    sort(bf, bf + n);
 
    do {
        sum = 0;
        for (int i = 0; i < n - 1; i++) {
            sum+= abs(bf[i] - bf[i + 1]);
        }
        //ans = max(ans,sum);
        if (ans < sum) ans = sum;
    }while(next_permutation(bf, bf + n));
    cout << ans << '\n';
 
    return 0;
}