[알고리즘] 백준 10819번: 차이를 최대로 (C++)

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

10819번: 차이를 최대로

범위가 8밖에 되지 않아서 백트래킹으로 나올 수 있는 수열들을 temp 배열에 담아 직관적으로 풀 수 있는 문제였다.

abs() == 절댓값 함수

#include <iostream>
#include <vector>
#include <cmath>
#define MAX 8 + 1
using namespace std;

vector<int> v;
vector<int> temp;
int n;
bool visited[MAX];
int maxValue = 0;

void sol(vector<int>& arr) {
	int sum = 0;
	for (int i = 0; i < n - 1; i++) {
		sum += abs(arr[i] - arr[i + 1]);
	}
	maxValue = max(sum, maxValue);
}

void backTrack(int cnt) {
	if (cnt == n) {
		sol(temp);
		/*
		for (int i = 0; i < temp.size(); i++) {
			cout << temp[i] << ' ';
		}
		cout << '\n';
		*/
	}

	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			visited[i] = 1;
			temp.push_back(v[i]);
			backTrack(cnt + 1);
			temp.pop_back();
			visited[i] = 0;
		}
	}
}

int main() {
	cin >> n;
	int value;
	for (int i = 0; i < n; i++) {
		cin >> value;
		v.push_back(value);
	}

	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			visited[i] = 1;
			temp.push_back(v[i]);
			backTrack(1);
			temp.pop_back();
			visited[i] = 0;
		}
	}

	cout << maxValue;

	return 0;
}