[BOJ] 10819번_차이를 최대로_브루트포스 (C++)

[문제]

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

N개의 정수로 이루어진 배열 A가 주어졌을 때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 문제이다.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

[사용 알고리즘]

브루트포스

[풀이 핵심]

• N의 값이 최대 8이므로 8가지 정수의 순열은 nPr = n!/(n-r)! = 8!이므로 40320가지이다. 따라서 브루트포스 알고리즘으로 해결해도 시간은 충분하다.
• algorithm헤더 파일에 있는 next_permutation()함수를 사용하면 쉽게 해결할 수 있다. next_permutation 함수는 매개변수로 vector의 이터레이터를 입력받고, 이터레이터 범위의 vector값의 순열을 사전순의 다음 순열로 바꾸고 true를 리턴한다. 그리고 사전순의 다음 순열이 없을 경우 false를 리턴한다. 이를 응용하여 오름차순으로 정렬되어 있는 순열을 do-while문을 이용해서 모든 조합의 순열을 만들 수 있다. 따라서 do-while문으로 새로운 조합의 순열을 만들고 해당 문제의 식에 대입해서 최대값을 갱신해주면 정답이다.

[코드]

//boj10819번_차이를 최대로_브루트포스 알고리즘

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	int N;
	cin >> N;

	vector<int> v;

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}

	sort(v.begin(), v.end());

	int result = 0;

	do {
		int sum = 0;

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

		result = max(result, sum);

	} while (next_permutation(v.begin(), v.end()));

	cout << result;

	return 0;
}