[BOJ] 13334. 철로

13334번: 철로

처음 생각했던 풀이는 각 (집, 사무실) 쌍을 시작점 기준으로 정렬한 후 각 쌍을 순회하며 뒤쪽의 끝점들만 따로 정렬한 후 upper_bound로 계산하기...였다. 잘 안 풀리는데다 좋은 풀이도 아닌 것 같아서 매주 일요일마다 진행하는 알고리즘 스터디에 가져갔는데, 이거 우선순위 큐 문제라는 얘기를 듣고 바로 풀이가 생각나서 뚝딱뚝딱 풀었다.

 

struct comp_second
{
    bool operator()(pair<int, int> a, pair<int, int> b)
    {
        if (a.second == b.second)
            return a.first > b.first;
        return a.second > b.second;
    }
};

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> f;
priority_queue<pair<int, int>, vector<pair<int, int>>, comp_second> s;

 

우선순위 큐를 두 개 만드는데, 하나는 시작점 기준으로, 하나는 끝점 기준으로 오름차순으로 정렬되는 큐이다.

 

cin >> N;
for (int i = 0; i < N; i++)
{
    int p, q;
	cin >> p >> q;
	if (p > q)
		swap(p, q);
	s.push({p, q});
}
cin >> D;
while (!s.empty())
{
	if (s.top().first + D < s.top().second)
	{
		s.pop();
		continue;
	}
	while (!f.empty() && s.top().second > f.top().first + D)
		f.pop();
	f.push(s.top());
	s.pop();
	cnt = max(cnt, (int)f.size());
}
cout << cnt;

 

모든 입력은 끝점 기준 큐 S에 넣고, 시작점 기준 큐 F는 처음에는 비어 있다.

S에서 값을 하나씩 빼서 F에 넣어주는데,  넣었을 때 총 길이가 D가 넘으면 F의 top값들을 총 길이가 D 이하가 될 때까지 뺀다.

이렇게 하면 F에 들어간 쌍들의 총 길이가 D 이하로 유지된다.

각 루프에서의 F의 길이 중 최댓값이 답이다.

 

같이 스터디를 한 친구의 풀이는, 각 쌍이 길이 D 안에 포함되는 철로의 시작점을 부등식으로 만들어서 각 부등식의 시작점과 끝점을 한꺼번에 정렬한 후 결과값에 시작점일 경우에 +1, 끝점일 경우에 -1을 하며 결과값의 최댓값을 구하는 풀이였다.

 

혼자서 고민할 땐 답이 잘 안 나오는데 같이 공부하면 왠지 풀이가 더 잘 떠오르는 느낌이다. 스터디 너무 재밌음.