[10819번] 차이를 최대로

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

10819번: 차이를 최대로

 

배열에 들어있는 정수의 순서를 적절히 바꿔서 문제에서 주어진 식의 최대값을 구해야 합니다.

수의 개수 제한이 N (3 ≤ N ≤ 8) 이므로 최대 8개의 수를 일렬로 나열하는 경우의 수는 \(8!\)이 됩니다.

\(8! = 40,320\)가지이므로 4만여정도는 모든 경우의 수를 다 계산해보아도 무리가 없습니다. (1억가지의 수가 대략 1초 소요)

모든 경우의 수를 찾아보기 위해 순열을 이용하는 브루트포스 알고리즘입니다.

 

모든 순열을 구하기 위해서는 정렬이 필수입니다.

순열 알고리즘에 대해 궁금하시다면 아래 글을 참조해주세요.

2022.02.12 - [Algorithms/백준 저지] - [10972,10973,10974번] 다음 순열, 이전 순열, 모든 순열

[10972,10973,10974번] 다음 순열, 이전 순열, 모든 순열

 

[코드]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int calc(vector<int> &a) {
    int sum = 0;
    for (int i = 0; i < a.size() - 1; i++) {
        sum += abs(a[i] - a[i + 1]); 
    }
    return sum;
}
int main () {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    int ans = 0;
    do {
        int t = calc(a);
        if(ans < t) ans = t; 
    } while(next_permutation(a.begin(), a.end()));
    cout << ans << '\n';
    return 0;
}

[결과]

6
20 1 15 8 4 10
62