알고리즘 문제풀이/백준문제풀이
[백준문제풀이] 10819 차이를 최대로
로디네로
2021. 1. 1. 15:58
반응형
풀이일시 : 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 후에 이들을 사용해준다.
[개념정리] STL _ 순열구하기 permutation
헤더파일을 추가하여 순열을 자동으로 구해줄 수 있다. 필요성 : 알고리즘 문제를 풀며 위 함수의 필요성을 느끼게 되었다. 모든 경우에 대해 순열을 바꿔주어 입력을 넣어줘야되는데 일일히
dbstndi6316.tistory.com
#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;
}
반응형