(c++)백준 10819번: 차이를 최대로

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

10819번: 차이를 최대로

[풀이]

N개의 정수로 이루어진 모든 순열을 식에 대입하여 그 결과값을 비교하여 최댓값을 구하였다. (Brute force)

수의 순서에 따라 결과값이 달라지므로 순열을 이용하였다.

#include <iostream>
#include <vector>
#include <algorithm>//max
#include <cstdlib>//abs
using namespace std;

int N;
int A[9];
vector<int>v;
int Max = -1;
bool Select[9];

//식에 대입
int Calc() {
	int res = 0;
	for (int i = 0; i < N - 1; i++) {
		res += abs(v[i] - v[i + 1]);
	}
	return res;
}

//순열 구하기
void dfs(int cnt) {
	if (cnt == N) {
		Max = max(Max, Calc());
	}

	for (int i = 0; i < N; i++) {
		if (Select[i])continue;
		Select[i] = true;
		v.push_back(A[i]);
		dfs(cnt + 1);
		Select[i] = false;
		v.pop_back();
	}
}

void solution() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	dfs(0);
	cout << Max << endl;
}

int main() {
	solution();
	return 0;
}