[BOJ 10819] 차이를 최대로 (C++)

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

10819번: 차이를 최대로

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

int arr[10];
bool visit[10];
int answer = -1;
vector<int> v;
int N;

int calc() {
	int sum = 0;
	for (int i = 0; i <= N - 2; i++) {
		sum += abs(v[i] - v[i + 1]);
	}
	return sum;
}

void dfs(int cnt) {
	if (cnt == N) {
		answer = max(answer, calc());
		return;
	}
	for (int i = 0; i < N; i++) {
		if (!visit[i]) {
			v.push_back(arr[i]);
			visit[i] = true;
			dfs(cnt + 1);
			visit[i] = false;
			v.pop_back();
		}
	}

}

int main() {
	memset(visit, false, sizeof(visit));
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	dfs(0);
	cout << answer << "\n";
	return 0;
}

 

순열 문제.

8!=4만 얼마로, 충분히 모든 경우의 수를 고려해서 최대값을 구할 수 있다.

순열은 늘 그렇듯이 dfs로 구해준다.