백준, BOJ, 11497번, 통나무 건너뛰기 C++ [CPP] ★★★

사실 그냥 이렇게 배치하면 무조건 최소로 될 것이다.라는 감이와서 한 것인데..

은근히 시간 오래걸렸다.

 

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

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;


//이웃하는 통나무의 최대 차이가 가장 적게 나는 배치 순서
// | x1 - x2 | 가 가장 작아야 한다. => 원형으로 배치되어있음
//통나무 개수는 10000개까지임
// 5개가 있다고 할 때 아래처럼 배치해야함. 즉, 첫번째를 중심으로 양쪽에 작은것부터 넣는다.
//     1
//  2    3
//   4  5
//덱을 이용하겠다.

int main(){
    int test;
    cin >> test;
    while(test--){
        int num;
        cin >> num;
        vector<int> logs;
        for(int i = 0; i<num; i++){
            int x;
            cin >> x;
            logs.push_back(x);
        }
        sort(logs.begin(), logs.end());
        
        deque<int> logsDeq;
        for(int i = 0; i<num; i++){
            if(i%2 == 0){
                logsDeq.push_front(logs[i]);
            }else{
                logsDeq.push_back(logs[i]);
            }
        }
        
        //전체를 순회하면서 차이 저장 (마지막 원소빼고)
        int diff = -123456789;
        for(int i = 0; i<num-1; i++){
            diff = max(abs (logsDeq[i] - logsDeq[i+1]), diff);
        }
        
        //첫번째 원소와 마지막 원소까지 비교
        diff = max(abs(logsDeq[num-1] - logsDeq[0]), diff);
        cout << diff << '\n';
        
    }
    
    
    return 0;
}

 

근데 보니까... 다른 풀이가 있는 것 같더라.

가 아니라 찾아보니 맞긴한데.. 그냥 방법만 다르더라.

감을 잘 잡았다고 할 수 있다.