백준 11497 c++ "통나무 건너뛰기" -PlusUltraCode-

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

[필자 사고]

처음에 이분탐색으로 접근해 보려다가 아이디어가 떠오르지 않았다.

그리디 관점으로 생각해보자 ..

정렬해 놓은 수를 기준으로 처음 idx를 새로운 배열에 맨 왼쪽 맨 오른쪽 번가라 넣게 되면

차이가 최소가 되지 않겠는가..??

 

괜찮은 아이디어 같아서 적용해 보았고 역시나 정답이였다. 

 

아래는 자세한 코드 해설이다.

[코드 해설]

통나무들을 원형으로 배열했을 때, 난이도는 인접한 통나무 높이 차이의 최댓값으로 정의된다. 따라서 목표는 이 최댓값을 최소화하는 배열을 찾는 것이다. 만약 단순히 오름차순으로 배열하면 양 끝의 통나무 차이가 커져 난이도가 커지게 된다.

이를 해결하기 위해 통나무 높이를 정렬한 뒤, 큰 값과 작은 값을 번갈아 배치하는 방식을 사용한다. 작은 값부터 시작해 양쪽 끝에 차례로 채워 넣으면, 인접한 통나무의 높이 차이가 고르게 분산되므로 최대 차이가 줄어든다. 결과적으로 이렇게 배치했을 때 난이도가 최소가 된다.

접근 방법

1. 통나무 높이를 입력받아 정렬한다.
2. 정렬된 결과를 이용해 새로운 배열을 만든다. 짝수 번째 원소는 왼쪽부터, 홀수 번째 원소는 오른쪽부터 채워 넣어 지그재그 형태가 되도록 배치한다.
3. 이렇게 완성된 배열을 원형으로 생각하고, 인접한 통나무들 간의 높이 차이를 모두 계산한다.
4. 이 중 가장 큰 값을 답으로 출력한다.

이 과정을 통해 원형 배열에서 발생할 수 있는 최대 높이 차이를 최소화할 수 있다.

[소스 코드]

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

int T;
int N;

int main(void) {
    cin >> T;
    while (T--) {
        cin >> N;
        vector<int> arr;
        vector<int> minimumArr(N);
        for (int i = 0; i < N; i++) {
            int num;
            cin >> num;
            arr.push_back(num);
        }

        sort(arr.begin(), arr.end());

        int left = 0;
        int right = N - 1;
        for (int i = 0; i < N; i++) {
            if (i % 2 == 0) {
                minimumArr[left++] = arr[i];
            }
            else {
                minimumArr[right--] = arr[i];
            }
        }

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

        cout << maxDiff << "\n";
    }
}