백준 10819: 차이를 최대로

배열에 들어 있는 값들을 이동시키며 바로 옆 칸과의 차이의 절대값의 최대를 출력하는 문제

조건에 주어진 수의 최대가 8인걸로 보아 시간복잡도가 복잡한 알고리즘도 대입할 수 있을 것으로 보인다. 그렇기 때문에 순열을 이용한 n!의 시간복잡도를 가지는 알고리즘을 사용한다. 시간복잡도는 순열을 구하는데 n! 그리고 각 순열을 구할 때마다 n번의 for문을 돌기 때문에 O(n*n!)의 값이 나온다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    int input;
    vector<int> perm;
    cin >> input;
    for (int i = 0; i < input; ++i)
    {
        int n_input;
        cin >> n_input;
        perm.push_back(n_input);
    }
    int ans = -500000;
    //첫 순열부터 시작하기 위해 정렬
    sort(perm.begin(), perm.end());
    do
    {
        int new_ans = 0;
        for (int i = 1; i < input; ++i)
        {
            new_ans += abs(perm[i] - perm[i - 1]);
        }
        ans = max(ans, new_ans);
    } while (next_permutation(perm.begin(), perm.end()));
    cout << ans << endl;
    return 0;
 
}