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

백준의 차이를최대로(10819) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제는 주어진 수열에서, 나올 수 있는 모든 순열의 경우를 모두 구해서 문제에서 주어진 식을 계산 후 최댓값을 찾으면

   되는 문제이다.

   이 문제가 순열인 이유는 수열이 { 1, 2, 3, 4} 로 주어진 경우 계산 값이 | 1 - 2 | + | 3 - 4 | = 2 가 되지만

   { 4, 1 , 3 , 2 } 로 계산을 하게 되면 | 4 - 1 | + | 3 - 2 | = 4로 같은 조합이더라도, 순서에 따라 결과값이 달라지기

   때문이다.

2) 모든 순열을 구하기만 한다면, 어렵지 않은 브루트 포스 문제가 될 것이다.

   순열을 구하는 법은 여기 를 참고 하자 !

   참고하였다면, 순열을 쉽게 구할 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
 
#define endl "\n"
#define MAX 8
using namespace std;
 
int N, Answer;
int Arr[MAX];
bool Select[MAX];
vector<int> V;
 
int Bigger(int A, int B) { if (A < B) return B; return A; }
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> Arr[i];
    }
}
 
//void Calculate()
//{
//    int Sum = 0;
//    for (int i = 0; i < N - 1; i++)
//    {
//        Sum = Sum + abs(Arr[i] - Arr[i + 1]);
//    }
//
//    Answer = Bigger(Answer, Sum);
//}
 
//void DFS(int Idx, int Cnt)
//{
//    if (Cnt == N)
//    {
//        /*for (int i = 0; i < N; i++)
//        {
//            cout << Arr[i] << " ";
//        }
//        cout << endl;*/
//        Calculate();
//        return;
//    }
//
//    for (int i = Idx; i < N; i++)
//    {
//        swap(Arr[i], Arr[Idx]);
//        DFS(Idx + 1, Cnt + 1);
//        swap(Arr[i], Arr[Idx]);
//    }
//}
 
void Calculate()
{
    int Sum = 0;
    for (int i = 0; i < V.size() - 1; i++)
    {
        Sum = Sum + abs(V[i] - V[i + 1]);
    }
    Answer = Bigger(Answer, Sum);
 
}
 
void DFS(int Cnt)
{
    if (Cnt == N)
    {
        Calculate();
        return;
    }
 
    for (int i = 0; i < N; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        V.push_back(Arr[i]);
        DFS(Cnt + 1);
        Select[i] = false;
        V.pop_back();
    }
}
 
void Solution()
{
    DFS(0);
    //DFS(0, 0);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}