백준 10819 : 차이를 최대로

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

1. 접근

• 모든 경우를 비교해볼 수 밖에 없으므로 브루트포스(brute force), 완전탐색 문제이다.
• 수학에서 배운 순열을 이용하면 금방 풀 수 있는 문제이다.
• 마침 STL 에 next_permutation 함수가 있으므로, 이를 이용해서 쉽게 풀 수 있다.

2. 나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int n;
    cin >> n;

    vector<int> arr;
    for (int i = 0; i < n; i++) {
        int tem;
        cin >> tem;
        arr.push_back(tem);
    }

    int ret = 0;
    sort(arr.begin(), arr.end());
    do {
        int tem = 0;
        for (int i = 0; i < arr.size() - 1; i++)
            tem += abs(arr[i] - arr[i + 1]);

        ret = max(ret, tem);
    } while (next_permutation(arr.begin(), arr.end()));

    cout << ret << "\n";

    return 0;
}

3. 참고

https://ansohxxn.github.io/algorithm/permutation/
직접 순열을 구현하는 좋은 예시