백준 10819 - 차이를 최대로(C++)

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

10819번: 차이를 최대로

 

풀이

입력으로 주어지는 배열의 원소 개수가 최대 8개이므로, 브루트포스로 하나하나 확인해가며 최댓값을 찾으면 된다.

이때 모든 경우의 수를 찾기 위해 next_permutation 을 사용했다.

입력받은 배열을 오름차순으로 정렬한 후, 계속해서 다음 순열을 찾으면서 원소들의 절댓값을 더한다.

끝날 때까지 반복하고 나면 max 변수에 최댓값이 저장된다.

 

코드

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

int absdiff(int a, int b)
{
    if(a>b) return a-b;
    else return b-a;
}

int main()
{
    int n;
    cin>>n;
    vector<int> v;
    int max=0;
    for(int i=0; i<n; i++)
    {
        int a;
        cin>>a;
        v.push_back(a);
    }
    sort(v.begin(),v.end());
    do{
        int sum=0;
        for(int i=0; i<n-1; i++)
        {
            sum+=absdiff(v[i],v[i+1]);
        }
        if(sum>max) max = sum;

    }while(next_permutation(v.begin(),v.end()));
    cout<<max;
    return 0;
}