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

 

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

 

문제는 간단하다

 

배열에 있는 값들에 대해 연속한 값 두개의 차이에 대한 절댓값을 모두 더한 값을 구하고

 

어떤 순서로 바꾸는 것이 가장 적은지에 대한 문제!

 

n이 8보다 작은수니까

모든 경우의수를 보면 될거고

그리고 각 경우의 수마다 값을 구하고 최댓값을 계속 비교하면 되는...?

 

이것도 순열문젠데?

https://lee-soo.tistory.com/17

[DFS] 백준 15649번 N과 M (1,2,3) (C++)

그렇다면 n,m 풀이에서 썻던 방법 그대로 사용하면 될듯,.,

 

왜냐면 

각 배열에 대한 순서에 대한 모든 경우의수를 구하니까!

 

그렇다면 순서는?

 

1. 배열에 대해 나올 수 있는 각 순열을 구한다.

2. 각 순열에 대해 해당 문제에서 설명한 식을 실행한다

3. 최댓값을 비교한다.

#include <iostream>

#include <cmath>

#include <algorithm>

#include <vector>

using namespace std;

int max1 = 0;

bool visited[10];

int arr[10];

vector<int> v;

void task(int n, int depth);

int main()

{

    int n;

    cin >> n;

    for (int i = 0; i < n; i++)

    {

        cin >> arr[i];

    }

    task(n, 0);

    cout << max1 << "\n";

}

void task(int n, int depth)

{

    if (depth == n)

    {

        int sum = 0;

        for (int i = 0; i < n - 1; i++)

            sum += (abs)(v[i] - v[i + 1]);

        max1 = max(max1, sum);

        return;

    }

    for (int i = 0; i < n; i++)

    {

        if (!visited[n])

        {

            visited[i] = true;

            v.push_back(arr[i]);

            task(n, depth + 1);

            v.pop_back();

            visited[i] = false;

        }

    }

}

 

배열에 대한 순열을 구하는 것 또한 n,m 시리즈에 나오니 꼭 참고하라.