[ SWEA 3503 ] 초보자를 위한 점프대 배치 (C++)

SWExpertAcademy의 초보자를 위한 점프대 배치 (3503 / D5) 문제이다.

[ 문제풀이 ]

점프대 간의 높이차 중에서 가장 큰 값을 최소화 시켜야 하는 문제이다.

처음에는 단순히 점프대를 정렬시켜서 일렬로 줄을 세워버리면 답을 쉽게 구할 수 있을 거라 생각했는데, 문제를 보게 되면

점프대를 원형으로 배치하기 때문에 이런 경우에는 답이 제대로 나오질 않는다.

예를 들어서 점프대의 높이가 { 3, 5, 2, 4, 1 } 인 5개의 점프대가 있고, 이를 정렬시키면 { 1, 2, 3, 4, 5 } 가 되는데,

이 때 높이차는 1이 아닌, 4가 되기 때문이다. 왜냐하면 0번 Index에 있는 점프대의 높이와, 4번 Index에 있는 점프대의 높이 차가

5 - 1 로 '4'가 되기 때문이다. 원형으로 배치하기 때문에 이 부분 까지 고려해 주어야 한다.

그래서 본인은 점프대를 정렬시킨 후, 순차적으로 앞쪽에 설치, 뒤 쪽에 설치 하는 과정을 반복해 주었다.

{ 3, 5, 2, 4, 1 } 이 있을 경우에는 { 1, 2, 3, 4, 5 } 로 정렬을 시킬 수가 있다.

이 후, 순차적으로 앞쪽, 뒤쪽 설치를 번갈아가면서 진행하는 것이다.

{ O , O , O , O , O } 이 5칸에 위에서 말했던 과정을 반복하면서 칸을 채워나가 보자.

첫 번째 '1' = 앞쪽에 설치

{ 1, O, O, O, O }

'2' = 뒤쪽에 설치

{ 1, O, O, O, 2 }

'3' = 앞쪽에 설치
{ 1, 3, O, O, 2 }

'4' = 뒤쪽에 설치

{ 1, 3, O, 4, 2 }

'5'는 앞쪽에 설치

{ 1, 3, 5, 4, 2 }

이렇게 될 것이다. 이 때 높이차의 최대는 '2'로 정답은 '2'가 된다.

0번 Index마저 앞/뒤 점프대의 높이차를 고려해야 되는 문제이기 때문에, 이렇게 앞뒤로 번갈아가면서 높이차가 최소인 값들을

순차적으로 설치해 줘야한다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
 
#define endl "\n"
#define MAX 10010
using namespace std;
 
int N, Answer;
int Jump[MAX];
int Arr[MAX];
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Initialize()
{
    Answer = 0;
}
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++) cin >> Jump[i];
}
 
void Solution()
{
    sort(Jump, Jump + N);
    int Idx = 0;
    int Left = 0;
    int Right = N - 1;
 
    while (Idx != N)
    {
        Arr[Left++] = Jump[Idx++];
        if (Idx == N) break;
        Arr[Right--] = Jump[Idx++];
    }
    for (int i = 0; i < N - 1; i++)
    {
        int Diff = abs(Arr[i] - Arr[i + 1]);
        Answer = Bigger(Answer, Diff);
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}