BOJ [C++]) 10819번 차이를 최대로

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

10819번: 차이를 최대로

 

1. 문제 

- N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

 

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

 

 

2. PS

- 가장 큰 수를 덱에 넣고 그 좌우로 가장 작은수와 다음 작은수를 넣음.

- 가장 작은수 옆에는 가장 큰 수의 다음 큰 수를 넣어서 풀려고 함 .. (설명 힘듬..)

- 주어진 배열이 홀수 일때는 마지막 수와 양 끝의 수를 비교해서 차이가 더 큰쪽으로 붙여줌.

#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;

int main() {
    int n;
    int sum = 0;
    deque<int> dq;
    deque<int> dq2;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int num;
        cin >> num;
        dq.push_back(num);
    }
    sort(dq.begin(), dq.end());
    
    dq2.push_back(dq.back());
    dq.pop_back();
    while(1) {
        dq2.push_back(dq.front());
        dq.pop_front();
        if(dq.size()==1) break;
        dq2.push_front(dq.front());
        dq.pop_front();
        if(dq.size()==1) break;
        dq2.push_back(dq.back());
        dq.pop_back();
        if(dq.size()==1) break;
        dq2.push_front(dq.back());
        dq.pop_back();
        if(dq.size()==1) break;
    }

     if(n%2) {
           if(abs(dq.back() - dq2.back()) > abs(dq.back()- dq2.front())) {
             dq2.push_back(dq.back());
         }
          else dq2.push_front(dq.back());
      }
     else dq2.push_back(dq.back());
    
    
    for(int i = 1 ; i < dq2.size(); i++) {
        int tmp = abs(dq2[i-1] - dq2[i]);
        sum += tmp;
    }

    cout << sum;
    
}

- 코드가 좀 더럽다..

- algorithm 라이브러리의 next_permutation를 사용하면 더 간편하게 짤 수 있었음.. (나중에 알았습니다.)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v;
    
    for(int i = 0 ; i < n; i++) {
        int num;
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());
    
    int ans = 0;
    while(next_permutation(v.begin(), v.end())) {
        int sum = 0;
        for(int i = 1 ; i < v.size(); i++) {
            sum += abs(v[i] - v[i-1]);
        }
        
        ans = max(sum, ans);
    }



    cout << ans;
    
}

-주의점은 next_permutation 함수를 사용하기 전에 sort를 해주어야 한다는 것.