백준 16359 Disks Arrangement

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

16359번: Disks Arrangement

 

풀이 

0. 문제를 풀기 앞서서 풀어야되는 문제

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

13433번: 기하 문제

 해당 문제를 통해서 너비를 구하는 법을 알아두는 것이 좋습니다.

 

1. 핵심 아이디어

위의 기하문제같은 경우는 브루트포스로 모든 경우를 구하면 되지만

해당 문제는 N이 매우크기 때문에 다른 방법을 사용해야합니다.

일단 문제에서 가장 큰원과 가장 작은원의 비율이 4이하라는 점에서 

 

다음 그림과 같이 원이 이전에 설치된 원이 아닌 다른 원에 접하는 경우가 없다는 것이 보장됩니다.

그렇기 때문에 바로 옆에 원만 고려해서 너비를 구하면 됩니다.

 

결론을 말하자면 해당 문제는 구성적부류의 문제로 특정 패턴대로만 원을 배치하면 정답을 구할 수 있습니다.

문제에 사용될 원들의 반지름을 오름차순으로 정렬한후

4가지 경우의 중에서 가장 작은 너비가 나오는 결과가 정답입니다.

 

max는 정렬시 가장 큰 수를 의미한다. 그리고 max-1은 2번째로 큰 수를 의미한다. (1은 가장 작은 수라는 의미겠죠?)

 

가운데를 기준으로 다음과 같은 순서로 배치해서 정답을 구하면됩니다.

코드

#include <bits/stdc++.h>

#pragma warning(disable:4996)

using namespace std;

#define endl "\n"
#define int long long
#define float long double

int n;
vector<float> arr;

//너비를 구하는 부분
float GetValue(deque<float> ar)
{
	float res = ar[0];

	for (int i = 1; i < n; i++)
		res += 2 * sqrt(ar[i] * ar[i - 1]);
	res += ar[ar.size() - 1];

	return res;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	std::cout.tie(NULL);

	cout << fixed;
	cout.precision(5);

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		arr.push_back(a);
	}
	sort(arr.begin(), arr.end());

	float ans = 1000000000000;

	//4가지의 경우의 수를 모두 고려하는 부분
	deque<float> q;
	for (int k = 0; k < 4; k++)
	{
		q.clear();
		for (int i = 0; i < n; i++)
			q.push_back(arr[i]);

		deque<float> dq;
		bool flag = false;
		while (!q.empty())
		{
			if (dq.empty())
			{
				if (k % 2 == 0)
				{
					dq.push_back(q.back());
					q.pop_back();
				}
				else
				{
					dq.push_back(q.front());
					q.pop_front();
				}
			}
			else if (flag == (k % 2 != 0))
			{
				int a = q.front();
				q.pop_front();
				if (k < 2)
					dq.push_front(a);
				else
					dq.push_back(a);
				if (q.empty())
					break;

				int b = q.front();
				q.pop_front();
				if (k < 2)
					dq.push_back(b);
				else
					dq.push_front(b);
				flag = !flag;
			}
			else
			{
				int a = q.back();
				q.pop_back();
				if (k < 2)
					dq.push_front(a);
				else
					dq.push_back(a);
				if (q.empty())
					break;

				int b = q.back();
				q.pop_back();
				if (k < 2)
					dq.push_back(b);
				else
					dq.push_front(b);
				flag = !flag;
			}
		}
		ans = min(ans, GetValue(dq));
		
	}
	cout << ans << endl;
}