[BOJ] 10819 - 차이를 최대로

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

---

[알고리즘풀이]

Input 범위가 작으므로, Backtracking을 이용해서 가능한 모든 배열 순서를 탐색한다.

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

vector<int> v;
bool check[8];
int n, ans = -1, A[8];

void bt(void) {
	if (v.size() == n) {
		int temp = 0;
		for (int i = 0; i < n - 1; i++) {
			temp += (int)(abs(A[v[i]] - A[v[i + 1]]));
		}
		if (temp > ans)
			ans = temp;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (check[i] == false) {
			v.push_back(i);
			check[i] = true;
			bt();
			check[i] = false;
			v.pop_back();
		}
	}
	return;
}
int main(void) {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> A[i];

	for (int i = 0; i < n; i++) {
		v.push_back(i);
		check[i] = true;
		bt();
		check[i] = false;
		v.pop_back();
	}
	cout << ans;

}

---