[백준 - 10819] 차이를 최대로 [c++]

 1.  문제

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

10819번: 차이를 최대로

 

2. 풀이과정

입력받은 n개의 수를 나열할 수 있는 모든 경우의 수에 대해 

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

위 식을 계산하며 최댓값을 갱신해주면 됩니다.

 

[코드 설명]

dfs함수는 n개의 수의 순서를 적절히 바꿔줍니다.

ex) n = 3, A = {1, 2, 3}

1 2 3

1 3 2

2 1 3

    .

    .

 

calculate함수는 나열된 수들을 이용해 

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|의 값을 계산해 줍니다.

 

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n;
vector<int> arr;
int result = -1;
bool visited[8];

int calculate(vector<int>& v) {
    int ret = 0;
    for(int i=0; i<=n-2; i++) ret += abs(v[i]-v[i+1]);
    return ret;
}

void dfs(vector<int>& v, int depth) {
    if(depth == n) {
        result = max(calculate(v), result);
        return;
    }
    for(int i=0; i<n; i++) {
        if(!visited[i]) {
            v.push_back(arr[i]);
            visited[i]=true;
            dfs(v, depth+1);
            v.pop_back();
            visited[i]=false;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i=0; i<n; i++) {
        int tmp;
        cin >> tmp;
        arr.push_back(tmp);
    }  
    vector<int> v;
    dfs(v, 0);
    cout << result;
    return 0;
}