3503. 초보자를 위한 점프대 배치하기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWGsV8IaAXsDFAVW&categoryId=AWGsV8IaAXsDFAVW&categoryType=CODE

SW Expert Academy

 

10000개 데이터로 10개 테스트 1초이므로 DFS는 절대 아닐거라고 생각.

그리디하게 풀려고 하는데 아이디어가 안떠올랐다.. 

정답 코드를 참조하니까 정렬후 가장 작은 수를 중간에 넣고 앞 뒤로 그보다 큰 수들을 차례로 배치하는 경우가

각 차이가 가장 최소가 되는 경우.

이렇게 정렬된 deque에서 최대값을 구하는 것이

배치중 최대값의 최소가된다.

#include<iostream>
#include<deque>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int N;
deque<int> de;
vector<int> vec;

int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{

		cin >> N;
        de.clear();
        vec.clear();
		for (int i = 0; i < N; i++)
		{
			int a;
			cin >> a;
			vec.push_back(a);
		}

		sort(vec.begin(), vec.end());
		for (int i = 0; i < vec.size(); i++)
		{
			if (i == 0)
			{
				de.push_back(vec[i]);
			}
			else
			{
				if (i % 2)
				{
					de.push_front(vec[i]);
				}
				else
				{
					de.push_back(vec[i]);
				}
			}
		}

		int result = 0;

		for (int i = 0; i < de.size(); i++)
		{
		
            if(i == de.size() -1)
			{
				int m = abs(de[de.size() - 1] - de[0]);
                 if(result < m)
                {
                    result = m;
                }
			}
			else
			{
				int m = abs(de[i] - de[i+1]);
                if(result < m)
                {
                    result = m;
                }
			}
		}

		cout << "#" << test_case << " " << result << endl;


	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}