[백준/c++] 10819번 - 차이를 최대로

문제

10819번: 차이를 최대로

풀이

분류 : 완전탐색

 

무작위로 나열된 수열에서

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

위 식의 최댓값을 구하는 문제입니다.

 

1. algorithm헤더의 next_permutation함수를 사용하여 무작위의 수열을 만듭니다.

2. 무작위로 만들어진 수열에 위의 식을 대입하여, 가장 큰 값이 나올때마다 최댓값을 갱신해줍니다.

 

코드(O(n+1)!) *O(n+1)!이 아니라면 알려주세요. 감사합니다(--)(__)*

	#include <iostream>
	#include <algorithm>
	#include <deque>
	#include <cmath>
	using namespace std;
	int main() {
	int n, m = 0;
	cin >> n;
	deque<int> arr(n);
	for (int i = 0; i < n; i++) cin >> arr[i];
	//모든 순열 구하기
	for (int i = 0; i < n; i++) {
	int curMax = 0;
	deque<int> temp(n);
	copy(arr.begin(), arr.end(), temp.begin());
	while (next_permutation(temp.begin(), temp.end())) {
	for (int k = 1; k < n; k++) curMax += abs(temp[k] - temp[k - 1]);
	m = max(curMax, m);
	curMax = 0;
	}
	arr.push_front(arr.back());
	arr.pop_back();
	}
	cout << m << endl;
	return 0;
	}

view raw 백준_10819_차이를최대로.cpp hosted with ❤ by GitHub