[백준] 10819번 차이를 최대로 C++ 코드

코드1 (next_permutaion 사용)

#include <iostream>
#include <algorithm>

using namespace std;

int n, a[10], res;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n);
	do {
		int tmp = 0;
		for (int i = 0; i < n - 1; i++) {
			tmp += abs(a[i] - a[i + 1]);
		}
		res = max(res, tmp);
	} while (next_permutation(a, a + n));
	cout << res << '\n';
	return 0;
}

코드2 (순열 구현)

#include <iostream>

using namespace std;

int n, a[10], res;

void permutation(int n, int r, int depth) {
	if (r == depth) {
		int tmp = 0;
		for (int i = 0; i < n - 1; i++) {
			tmp += abs(a[i] - a[i + 1]);
		}
		res = max(tmp, res);
	}
	for (int i = depth; i < n; i++) {
		swap(a[i], a[depth]);
		permutation(n, r , depth + 1);
		swap(a[i], a[depth]);
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	permutation(n, n, 0);
	cout << res << '\n';
	return 0;
}

풀이

n의 최대 크기가 8이므로, 순열을 통해 직접 찾아줘도 충분하다. (8!은 40320)