[백준] 알고리즘 10819번 - 차이를 최대로문제

문제

https://www.acmicpc.net/problem/10819

10819번: 차이를 최대로

소스코드

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
vector<int> v;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        v.push_back(x);
    }
    sort(v.begin(), v.end());
    int sum = 0;
    do {
        int temp = 0;
        for (int i = 0; i < n-1; i++) {
            temp += abs(v[i] - v[i + 1]);
        }
        sum = max(sum, temp);
    } while (next_permutation(v.begin(), v.end()));
    cout << sum;
}

해설

같은 숫자를 뽑았을 경우 순서에 따라서 결과가 다르다.

모든 경우의 수를 해봐도 8! 밖에 안되기 때문에 모든 순열을 살펴보면서 비교해보면된다.

먼저 첫 시작 순열을 결정해주기 위해서 정렬을 해준다음 next_permutation을 이용하여 모든 경우의 수를 비교해보았다.