백준 13334: 철도

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

 

기발한 아이디어?

이 문제를 보며 관찰한 결과, 철로 위치의 끝은 적어도 한 사람의 집과 사무실 끝을 둘 것이라 생각했다.

그렇다면, Set을 사용해서, 각 사람의 집과 사무실 위치를 저장해서 중복을 제거한 다음

(해당 위치 +- 철로 길이) 내에 얼마나 많은 출근 길이 겹치는 지 확인하면 정답일 것이다.

#include <iostream>
#include <set>
#include <algorithm>
#include <vector>

using namespace std;
vector<pair<int, int>> P;
int N, H, O, D, cnt = 0, ans = 0;
set<int> S;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> H >> O;
		if (H > O) swap(H, O);
		P.push_back({ H, O });
	}
	sort(P.begin(), P.end());
	cin >> D;
	for (int i = 0; i < N; i++)
	{
		S.insert(P[i].first - D);
		S.insert(P[i].first);
		S.insert(P[i].second - D);
		S.insert(P[i].second);
	}
	auto iter = S.begin();
	for (int i = 0; i < N;)
	{
		if (P[i].second - P[i].first > D)
			++i;
		else if (P[i].first >= *iter && P[i].second <= (*iter) + D)
		{
			++cnt;
			++i;
		}
		else
		{
			ans = max(cnt, ans);
			cnt = 0;
			++iter;
		}
	}
	ans = max(cnt, ans);
	cout << ans << '\n';
}

하지만, 막상 구현을 시도 하려니, 막막해졌다. 막연히 스위핑 혹은 슬라이딩 윈도우를 사용하면, 어떻게든 될것이라 생각했는데, 결국엔 실패했다.

 

스위핑에서 다시 시작

결국 처음부터 다시 시작했다. 만약 이 문제가 스위핑 문제라면, 어떻게 해결할까? 일단 출근길을 시작 구간 순으로 정렬할 것이다. 스위핑을 하며, 현재의 선분과 다음 선분을 합치고(예로 1 3과 5 8을 합치면 현재 선분은 1 8이 된다.), 그 선분이 철로 길이 L보다 작으면 어떻게 할까?

 

처음엔 현재 선분을 버릴까 생각했는데, 현재 선분 중간에 정답이 될 가능성이 있다. 그러면 이전의 선분들의 시작 점들을 저장하고, 현재 선분이 L보다 작을때 까지 현재 선분의 시작점을 그 점들의 시작점으로 두면 정답이지 않을까? 이 아이디어를 바탕으로 구현을 시도했다.

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
vector<pair<int, int>> P;
int N, H, O, D, cnt = 0, ans = 0, l, r = 0;
queue<int> q;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> H >> O;
		if (H > O) swap(H, O);
		P.push_back({ H, O });
	}
	sort(P.begin(), P.end());
	cin >> D;
	for (int i = 0; i < N; i++)
	{
		if (P[i].second - P[i].first > D) continue;
		while (!q.empty() && P[i].second - q.front() > D)
		{
			--cnt;
			q.pop();
		}
		q.push(P[i].first);
		++cnt;
		ans = max(ans, cnt);
	}
	ans = max(ans, cnt);
	cout << ans << '\n';
}

반례

혹시 내 코드가 틀리지 않을까 불안해진 나는 질문 게시판에 반례가 없는지 들여다보았다. 그러자, 반레를 하나 발견하였다.

 

4
1 4
1 4
2 5
3 4
3

 

이 예시의 정답은 3인데, 내 코드는 2로 표시하였다.

이것을 바탕으로 생각해본 결과, 정렬이 잘못된 것을 발견하였다.

기존의 스위핑 방식대로, 시작 구간 순으로 정렬하였는데, 이 문제의 경우 끝 구간 순으로 정렬해야한다. 그래야 선분을 합칠 때, 해당 구간 내의 겹치는 구간을 제대로 카운팅할 수 있다.

그리고, 시작 위치는 기존 코드와 달리 둘숙날숙 할 수 있으니 Queue를 Priority_Queue로 수정한다.

 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
vector<pair<int, int>> P;
int N, H, O, D, cnt = 0, ans = 0, l, r = 0;
priority_queue<int> q;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> H >> O;
		if (H > O) swap(H, O);
		P.push_back({ O, H });
	}
	sort(P.begin(), P.end());
	cin >> D;
	for (int i = 0; i < N; i++)
	{
		if (P[i].first - P[i].second > D) continue;
		while (!q.empty() && P[i].first + q.top() > D)
		{
			--cnt;
			q.pop();
		}
		q.push(-P[i].second);
		++cnt;
		ans = max(ans, cnt);
	}
	ans = max(ans, cnt);
	cout << ans << '\n';
}

간만에 재미있는 스위핑 문제였다.