[백준] 10819번 차이를 최대로

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

10819번: 차이를 최대로

N (3 ≤ N ≤ 8)이라는 것부터가 이거는 노가다로 풀으라는 것이다. 순열로 풀었다. (백트래킹)

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

using namespace std;

int n;
vector<int> v;
vector<bool> visited;
int maxSum = 0;

void permutation(int num, vector<int> result) {
	if (n == num) {
		int sum = 0;
		for (int i = 0; i < n - 1; i++) {
			sum += (abs(result[i] - result[i + 1]));
		}
		if (sum > maxSum)
			maxSum = sum;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			visited[i] = true;
			result[num] = v[i];
			permutation(num + 1, result);
			visited[i] = false;
		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n;
	v = vector<int>(n);
	visited = vector<bool>(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	permutation(0, vector<int>(n));
	cout << maxSum;
	return 0;
}