DAY4 중급 - 백준 10819번 (C++)

www.acmicpc.net/problem/10819

10819번: 차이를 최대로

 

<답안>

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int array[8] = {0};
    int n;
    int sum = 0;
    int temp = 0;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>array[i];
    }
    sort(array,array+n);
    do
    {
        for(int i=0; i<n-1; i++)
        {
            temp += abs(array[i] - array[i+1]);
        }
        sum = max(sum,temp);
        temp = 0;
    }while(next_permutation(array, array+n));

    cout<<sum;
}

 

<설명>

계속 생각을 하다가 규칙을 찾긴 했지만 구현하는데 힘들어 좀더 고민을 하다가

약간의 편법?을 사용하였다 그래서 기회가 되면 다시 풀어볼 생각이다

 

사용한 편법은 수열의 내용들을 서로 자리를 바꿀수 있는 모든 경우의 수 (n!) 를 돌려보며

각 케이스에 해당되는 값을 temp로 구한다음

지금까지 temp값들중 최대값이였던 max와 비교를 하여 큰경우 max를 바꾸는 식이다

 

말그대로 그냥 모든 케이스 중에 최대값을 출력한다는 개념이다...

 

이 개념이 가능했던 이유는 next_permutaion(array,array+n) 이 코드는

n개의값이 있는 array배열을 수시로 모든경우로 자리바꿈을 해주는 매소드이다

사용하기에 앞서 오름차순으로 먼저 정렬이 되어있기만 하면 된다

 

그래서 다음번엔 다시 풀어보겠다