[백준] 20665 - 독서실 거리두기

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

20665번: 독서실 거리두기

 

아주 최적의 그럴듯한 방법이 있을 것 같지만 사실 시간(분 단위)의 범위가 1440분이라 단순 구현 + 시뮬레이션을 진행하면 된다.

 

1. 입력을 받고, 시작 시간 기준 오름차순, 끝나는 시간 기준 오름차순으로 정렬한다.
2. 손님을 정렬된 순서에 따라 탐색하며 앉을 수 있는 좌석의 번호를 구한다.
   • 모든 좌석을 탐색하며 앉을 수 있는 좌석 중에 가장 가까이에 있는 사람의 거리가 최대가 되는 좌석을 탐색한다.
   • 이때, 그러한 좌석이 여러 개가 있다면 가장 번호가 낮은 좌석을 선택한다.
3. 고른 좌석의 번호를 [시작 시간, 끝나는 시간)에 기입해 사용하고 있다는 것을 표시한다.
4. 09:00부터 21:00까지 모든 시간을 탐색해 관리자가 앉고 싶어 하는 자리가 비어있는 시간이 얼마인지 탐색한다.

 

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

int n, t, p;
int ti[501][1441];
pair<int, int> a[500];

bool compare(pair<int, int> p1, pair<int, int> p2)
{
	if (p1.first == p2.first)
	{
		return p1.second - p1.first < p2.second - p2.first;
	}
	return p1.first < p2.first;
}

int getNumber(int now)
{
	int res = 0, maxL = 0;
	for (int i = 1; i <= n; i++)
	{
		if (ti[i][now])
		{
			continue;
		}
		int left = i - 1, right = i + 1;
		while (left > 0 && ti[left][now] == 0)
		{
			left--;
		}
		if (left == 0)
			left = 1000000000;
		else
			left = i - left;
		while (right <= n && ti[right][now] == 0)
		{
			right++;
		}
		if (right == n + 1)
			right = 1000000000;
		else
			right = right - i;
		int offset = min(left, right);
		if (maxL < offset)
		{
			maxL = offset;
			res = i;
		}
	}

	return res;
}

int main()
{
	cin >> n >> t >> p;

	for (int i = 1; i <= t; i++)
	{
		string start, end;
		cin >> start >> end;
		a[i] = {stoi(start.substr(0, 2)) * 60 + stoi(start.substr(2)), stoi(end.substr(0, 2)) * 60 + stoi(end.substr(2))};
	}

	sort(a + 1, a + 1 + t, compare);

	for (int i = 1; i <= t; i++)
	{
		int start = a[i].first;
		int end = a[i].second;
		int num = getNumber(start);
		if (num != 0)
		{
			for (int j = start; j < end; j++)
			{
				ti[num][j] = i;
			}
		}
	}

	int ans = 0;

	for (int i = 9 * 60; i < 21 * 60; i++)
	{
		if (ti[p][i] == 0)
		{
			ans++;
		}
	}

	cout << ans;
}