[백준] 10819번 차이를 최대로 , 순열문제

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

10819번: 차이를 최대로

입력받은 값을 오름차순 정렬한 후, 순열로 나열해 모든 경우를 탐색하며 조건에 맞는 합이 가장큰 값을 출력해주면 된다.

하지만 처음 접근을 숫자를 하나씩 바꿔보며 문제에 주어진 조건에서의 합이 최대인 경우에 swap을 해주는 경우로 생각했다.

모든 test case를 커버할 수 없어서 최대합이 나오지 않았다.

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

int main()
{

    vector<int> m;
    int cnt;
    cin >> cnt;
    int im;
    for (int i = 0; i < cnt; i++)
    {
        cin >> im;
        m.push_back(im);
    }

    sort(m.begin(), m.end());
    int sum = 0;
    int imsi = 0;
    do
    {
        for (int i = 0; i < cnt; i++)
        {
            if (i == cnt - 1)
                break;
            imsi += abs(m[i] - m[i + 1]);
        }
        sum = max(sum, imsi);
        imsi = 0;

    } while (next_permutation(m.begin(), m.end()));

    cout << sum;

    return 0;
}