[백준문제풀이] 10819 차이를 최대로

 

풀이일시 : 2020-10-15

​

 

문제 :

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

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

​

​

입력 :

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

ex)

6

20 1 15 8 4 10

​

​

출력 :

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

ex)

62

​

​

풀이 :

숫자의 순서를 모두 섞어줘야한다. C++ STL에는 이를 수행하기 위한 매우 편한 방법이 존재한다. next_permutation과 prev_permutation이다. sort 후에 이들을 사용해준다.

 

dbstndi6316.tistory.com/34

[개념정리] STL _ 순열구하기 permutation

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
	int N,s,temp;
	int arr[8];
	int sum = 0;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> s;
		arr[i] = s;
	}

	sort(arr, arr + N);
	
	do {
		temp = 0;
		for (int i = 0; i < N - 1; i++) {
			temp += abs(arr[i] - arr[i + 1]);
		}
		sum = max(sum, temp);
	} while (next_permutation(arr, arr + N));
	//순열을 바꿔주는 함수이다.
	
	cout << sum << endl;
}
​