[백준] 10819번 차이를 최대로

문제

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

풀이과정

완전탐색을 순열로 구현해서 푼 문제다. N의 범위가 작기 때문에 순열로 완전탐색을 해도 시간초과가 나지 않을 수 있다.
보통 N이 10이하면 순열로 문제를 풀어도 된다고 한다.

먼저 입력받은 배열을 sort()를 통해 정렬을 해준 후 next_permutation을 통해서 모든 순열을 돌면서 가장 차이가 큰 값을 찾는다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int calculate(vector<int> &a)
{
    int result = 0;

    for (int i = 1; i < a.size(); i++)
    {
        result += abs(a[i - 1] - a[i]);
    }

    return result;
}

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

    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 tmp = calculate(a);
        ans = max(ans, tmp);
    } while (next_permutation(a.begin(), a.end()));

    cout << ans << "\n";

    return 0;
}