[백준/c++] 10819번: 차이를 최대로

문제 링크 -https://www.acmicpc.net/problem/10819

🌱 문제

🌱 풀이

• 모든 수열 문제랑 비슷하다.
• 모든 수열 경우에서의 절댓값의 합을 전부 구해서 max값을 출력해야겠다고 생각하였다.
• 시간 복잡도는 수열은 N!개 존재하고, 각각의 합을 구하는 데에는 O(N)이므로, 총 O(N!*N)의 시간이 소요되어서 3<=N<=8 범위에서는 아주 충분하다.
• 벡터를 입력받은 후 먼저 정렬을 하고, next_permutation 함수를 통해 가능한 수열 전부의 경우에서 합을 구했다.
• 마찬가지로 next_permutation 함수 진입전에 첫 수열일때도 답을 구해야 하므로 do_while을 이용했다.

🌱 코드

//10819번: 차이를 최대로
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> v;
int n;
int answer;

int func(vector<int> v, int n){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int sum=0;
    for(int i=1; i<n; i++){
        int diff=v[i]-v[i-1];
        if(diff<0)
        diff=-diff;

        sum+=diff;
    }
    return sum;
}

int main(){
    int result=0;

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>n;
    for(int i=0; i<n; i++){
        int x;
        cin>>x;
        v.push_back(x);
    }
    sort(v.begin(),v.end());
//     for(int i=0; i<n; i++){
//         cout<<v[i]<<" ";
//     }
//     cout<<"\n";

    int cnt=0;
    do{
        // cout<<"cnt : "<<cnt <<"\n";
        // cnt++;
        result = func(v,n);
        if(result>answer)
        answer=result;
    }
    while(next_permutation(v.begin(),v.end()));

    cout<<answer<<"\n";
}