백준 10819번: 차이를 최대로

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

10819번: 차이를 최대로

 

이 문제를 풀면서 처음 든 생각은 주어진 크기의 범위가 배우 적다라는 것이다 . 실제로 입력값 n의 범위가 (3<=n<=8)

이므로 모든 배열을 둘러보아도 크기가 8!=40320 이다 즉 시간에는 매우 넉넉 하다는 것이고 브루트포스(완전 탐색)으로도 가능하다는 것이다.

이 문제로 next_permutation함수를 처음 접하게 되었다.

 next_permutation함수란?

주어진 배열 a 1,2,3,4가 있을 떄 이 함수 next_permutation(a.begin(),a.end())를 사용 할 경우 다음 순열(1-2-3-4의 다음 순열은 1-2-4-3) 이 배열에 저장되고 true가 반환이 된다.

즉 이 함수를 끝까지 돌려보면

1 2 3 4
1 2 4 3
1 3 2 4

...

4 2 3 1
4 3 1 2
4 3 2 1

이렇게 나오고 마지막 4 3 2 1 이 될 경우 다음 순열이 없기 때문에 false를 반환한다.

즉 이 순열함수를 계속 사용하면 그 함수의 순열을 전부 탐색 가능하다. (단 정렬해야함)

이제 완전탐색으로 하고 순열함수도 알았으니 코드를 보자

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector> 
using namespace std;
int calculate(vector<int>& a){         //값 계산하기
    int sum=0;
    for(int i=1;i<a.size();i++){
        sum+=abs(a[i]-a[i-1]);
    }
    return sum;
}
int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin >>a[i];
    }
    sort(a.begin(),a.end());
    int ans=0;
    do{
        int temp=calculate(a);
        ans=max(ans,temp);
    }while(next_permutation(a.begin(),a.end()));              //모든 순열 돌아보기
    cout <<ans;
    return 0;
}