[순열] BOJ 10819 차이를 최대로

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

10819번: 차이를 최대로

- 문제 파악

정수 N이 주어지고 N개의 수열이 주어진다. 이 수열을 적절히 조합하여 아래 식으로 계산 하였을때 최대값을 출력하라.

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

 

-정답

아래 식을 대충봐서 처음에 이해가 안됐지만 자세히 보니 N-2 까지 자기 자신과 다음 수열과의 차에 대한 절대값을 계속 더하는 공식이다.

사전순으로 찾아가기 위해 받은 수열을 먼저 오름차순으로 정렬했다.

#include "bits/stdc++.h"

using namespace std;

int arr[10001];
int ans;

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin>>arr[i];
    }

    sort(arr, arr + n);

    bool bwhile = true;

    while (bwhile)
    {
        int tmp = 0;
        for (int i = 0; i < n-1; i++)
        {
            tmp += abs(arr[i] - arr[i + 1]);
        }

        ans = max(tmp, ans);
        bwhile = next_permutation(arr, arr + n);
    }

    cout << ans;

}

// 20 1 15 8 10 4