[백준] 11497번 통나무 건너뛰기 (C++)

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

 

 

이 문제는 통나무의 배열이 존재할때 원형으로 놓아서 그 사이 차가 최솟값이 나오도록 하는 문제이다.

 

원형으로 놓기 때문에 양끝값이 서로 이어져있다.

 

 

이 문제를 풀기 위해서 배열을 최소 차이로 놓아야 한다고 생각했다 

떠오른 아이디어는 가장 큰 값을 중앙에 놓고 그다음 큰 값을 중앙 오른쪽 이후 큰 값을 중앙 왼쪽

 

이렇게 계속 오른쪽 왼쪽으로 놓는 것이 차이값을 최소로 만드는 것이라고 생각하여

최대힙을 사용하여 값을 넣은 후 중간 인덱스에서부터 값을 계속 넣어주었다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    string s;
    vector<int> v;
};

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int T, N;
int arr[10001];
int tmp[10001];
priority_queue<int, vector<int>> pq;

void solve() {
    int idx = N / 2;
    int x = pq.top();
    pq.pop();
    int cnt = 1;
    tmp[idx] = x;

    while(!pq.empty()) {
        int maxval = pq.top();
        pq.pop();
        int minval = pq.top();
        pq.pop();

        tmp[idx+cnt] = maxval;
        tmp[idx-cnt] = minval;

        cnt++;

        if(pq.size() == 1) {
            int temp = pq.top();
            pq.pop();
            tmp[idx-cnt] = temp;
        }
    }

    int result = 0;

    for(int i = 1; i < N; i++) {
        result = max(result, abs(tmp[i] - tmp[i-1]));
    }
    result = max(result, abs(tmp[N-1] - tmp[0]));

    cout << result << endl;
}

void input() {
    cin >> T;

    while(T--) {
        cin >> N;

        for(int i = 0; i < N; i++) {
            cin >> arr[i];
            pq.push(arr[i]);
        }

        solve();
        memset(arr, 0, sizeof(arr));
        memset(tmp, 0, sizeof(tmp));
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
}