[백준] 2594: 놀이공원

문제 링크

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

접근 방식 / 풀이

입력받은 시간의 앞, 뒤로 10분씩을 더하여 미리 저장해둔다.
이들을 시작 시간이 작은 순으로 정렬해둔 다음, 종료 시간 ~ 다음의 첫 시간의 차를 구하여 max를 구한다.

이런 로직이 오류 없이 사용되기 위해서는 조건이 필요한데,
한 놀이기구의 운행 시간에 포함되는 다른 기구는 존재해서는 안된다.
즉, 1000 ~ 1300 에 운행하는 놀이기구가 있을 때, 1100 ~ 1200 에 운행되는 놀이기구가 존재한다면,
정렬했을 때 후자가 뒤에 오게 되므로, 사실상 max로 가능한 값은 1310 ~ 2200임에도 불구하고 1210 ~ 2200의 값이 max보다 크기 때문에 정답이 아닌 값이 도출된다.

해당 조건만 충족된다면, 가능한 경우는 다음과 같다.
a ~ b
c ~ d
라는 값이 정렬되어 있을 때,

1. a = c && b < d
2. a < c && b < d

위 경우밖에 가능하지 않으며, 따라서 정렬된 순대로 종료시간 ~ 다음의 첫 시간의 차를 통해 max를 구할 수 있다.

---

답안 코드 링크 (Github)

Github Solution Link

정답 코드 (C++)

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

vector<pair<int, int>>	times;
void	fastio(void);
void	push(int start, int end);
int		diff(int start, int end);

int main(void)
{
	int	num, max = 0;
	int	begin = 1000, fin = 2200;
	int	start, end;

	fastio();
	cin >> num;
	for (int i = 0; i < num; i++)
	{
		cin >> start >> end;
		push(start, end);
		for (int j = 0; j < times.size() - 1; j++)
		{
			if ((diff(times[j].first, times.back().first) && diff(times.back().second, times[j].second)) \
                || (diff(times.back().first, times[j].first) && diff(times[j].second, times.back().second)))
			{
				times.pop_back();
				break;
			}
		}
	}
	sort(times.begin(), times.end());
	max = diff(begin, times[0].first);
	if (max < diff(times.back().second, fin))
		max = diff(times.back().second, fin);
	for (int i = 0; i < times.size() - 1; i++)
		if (max < diff(times[i].second, times[i + 1].first))
			max = diff(times[i].second, times[i + 1].first);
	cout << max << "\n";
	return (0);
}

void	push(int start, int end)
{
	int	s_time = start / 100;
	int	s_min = start % 100;
	int	e_time = end / 100;
	int	e_min = end % 100;
	int	diff = 0;

	s_min -= 10;
	if (s_min < 0)
	{
		s_min += 60;
		s_time--;
	}
	e_min += 10;
	if (e_min >= 60)
	{
		e_min -= 60;
		e_time++;
	}
	times.push_back({ s_time * 100 + s_min, e_time * 100 + e_min });
}

int	diff(int start, int end)
{
	int	s_time = start / 100;
	int	s_min = start % 100;
	int	e_time = end / 100;
	int	e_min = end % 100;
	int	diff = 0;

	if (s_time <= e_time)
	{
		diff += (e_time - s_time) * 60;
		diff += e_min - s_min;
	}
	return (diff >= 0 ? diff : 0);
}

void	fastio(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}