10819번

10819번 - 차이를 최대로

이 문제는 N 제한이 작기 때문에 완전탐색을 통해서 충분히 풀 수 있다.

예전에는 강의를 보고 next_permutation 으로 풀었으나, next_permutation 함수에 대한 이해가 부족해서 스스로 재귀를 통해

permutation 을 구현해서 풀어보았다.

인덱스 값을 재귀함수를 통해서 변화시켜준다. 이때, used 함수를 이용한다.

그 뒤 구한 permutation 이 N 과 일치하면 cal 함수를 통해서 최대값을 구한다.

next_permutation 함수는 정렬한 뒤에 이용해야한다.

이유는 

http://alhena.tistory.com/43

에서 잘 설명해주신다.

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, ans = 0;
bool used[9];
vector<int> S;
vector<int> tmp;
 
int cal(vector<int>& tmp)
{
    int sum = 0;
    for (int i = 1; i<tmp.size(); i++)
    {
        sum += abs(tmp[i] - tmp[i - 1]);
    }
 
    return sum;
}
void permu(int len,vector<int>& tmp)
{
    if (len == N)
    {
        ans=max(ans, cal(tmp));
        return;
    }
 
    for (int i = 0; i < N; i++)
    {
        if (!used[i])
        {
            tmp.push_back(S[i]);
            used[i] = true;
            
            permu(len + 1,tmp);
 
            tmp.pop_back();
            used[i] = false;
        }
    }
 
    return;
}
int main()
{
    cin >> N;
    for (int i = 0; i<N; i++)
    {
        int a;
        cin >> a;
        S.push_back(a);
    }
    vector<int> tmp;
    permu(0,tmp);
 
    cout << ans << endl;
 
 
    return 0;
}

<정답 코드 - next_permutation 함수 사용>

    
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N;
vector<int> S;
 
int cal()
{
    int sum = 0;
    for (int i = 1; i<S.size(); i++)
    {
        sum += abs(S[i] - S[i - 1]);
    }
 
    return sum;
}
int main()
{
    cin >> N;
    for (int i = 0; i<N; i++)
    {
        int a;
        cin >> a;
        S.push_back(a);
    }
    sort(S.begin(), S.end());
 
    int ans = cal();
    do
    {
        int k = cal();
        if (ans < k)
        {
            ans = k;
        }
    }
    while (next_permutation(S.begin(), S.end()));
 
    cout << ans << endl;
 
 
    return 0;
}