백준 10819. 차이를 최대로

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

10819번: 차이를 최대로

 

주어진 수들로 만들수 있는 모든 순열을 만든후 식을 계산해서 최댓값을 갱신한다.

 

순열을 next_permutation 함수로 만듦:

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

int n;
int ans = 0;
vector<int> v;

// 만들어진 순열로 식을 계산한다
int Calculate()
{
    int sum = 0;
    for(int i = 0; i < n-1; i++)
    {
        int n1 = v[i];
        int n2 = v[i+1];

        sum += abs(n1 - n2);
    }
    return sum;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int num;
        cin >> num;
        v.push_back(num);
    }

    // 모든 순열 탐색위해 먼저 오름차순으로 정렬
    sort(v.begin(), v.end());

    // 만들수 있는 모든 순열을 만들어서 식의 최댓값을 계산한다
    do {
        ans = max(ans, Calculate());
    } while(next_permutation(v.begin(), v.end()));

    cout << ans;

}

 

순열을 dfs로 만듦:

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

int n;
vector<int> v;
vector<int> res;
bool mark[10];
int ans = 0;

// 만들어진 순열로 식을 계산한다
int Calculate()
{
    int sum = 0;
    for(int i = 0; i < n-1; i++)
    {
        int n1 = res[i];
        int n2 = res[i+1];

        sum += abs(n1 - n2);
    }
    return sum;
}

void dfs(int depth)
{
    // 순열 만들어짐
    if(depth == n)
    {
        ans = max(ans, Calculate());

        return;
    }

    for(int i = 0; i < n; i++)
    {
        if(mark[i]) continue;
        mark[i] = true;
        res.push_back(v[i]);

        dfs(depth+1);

        mark[i] = false;
        res.pop_back();
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int num;
        cin >> num;
        v.push_back(num);
    }

    dfs(0);

    cout << ans;
}