[10819번] 차이를 최대로

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 순열(Permutation) 이용

이 문제의 입력 조건은 다음과 같다.

- 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 

- 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

즉, 그냥 하나하나 모두 비교해 봐도 시간이 남는 문제이다.

따라서 이 문제는 순열을 이용하여 해결 해 볼 수 있다.

순열 소스코드는 아래 주소에 있다.

http://www.crocus.co.kr/306

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

#include <iostream> #include <math.h> #define swap(a,b){int tmp = a; a = b; b = tmp;}   using namespace std;   int arr[10]; int n; int val, _max;   int getvalue() {     for (int i = 1; i < n; i++)         val += abs(arr[i] - arr[i - 1]);       return val; }   // k 는 시작점, a[k],...,a[m]에 대한 모든 순열을 생성 void permutations(int *a, const int k, const int m)                                                      {     int i;     int temp;         if (k == m) //순열이 완성되었을 때 수행 할 일     {         int ans = getvalue();           ans > _max ? _max = ans : 0;           val = 0;     }       else // a[k] a[m]에 있는 여러 순열을 순환적으로 생성     {         for (i = k; i <= m; i++)         {             swap(a[k], a[i]); // a[k]와 a[i]를 교환             permutations(a, k + 1, m); // a[k+1],...a[m]에 대한 모든 순열                                        // 원래 상태로 되돌리기 위해 a[k]와 a[i]를 다시 교환             swap(a[k], a[i]);         }       } }   int main() {     cin >> n;       for (int i = 0; i < n; i++)         cin >> arr[i];       permutations(arr, 0, n-1);          cout << _max; } //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus