백준 2024: 선분 덮기

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

 

스위핑의 방법

이 문제는 꽤 고민을 하였다.

정렬을 한 뒤, 스위핑을 하면 될 것 같은데 스위핑을 어떻게 해야할지가 문제였다.

단순히 스위핑을 하면 [0, M]을 덮는 최소의 선분 갯수를 구할 수 없어서 특수한 방법이 필요할 것 같다.

 

일단 나는 이 문제를 해결하기 위해서, 예시 하나를 만들었다.

 

10

-1 5

3 7

4 10

0 0

답: 2

 

이 문제를 근본적으로 해결할 수 있는 예시라 생각했기 때문이다.

 

여러 시도

이렇게 생각을 하니, 우선 선분을 왼쪽 끝 순서대로 sort한 뒤에, 순서대로 오른쪽 끝을 우선순위 큐에 저장해서 현재 선분과 왼쪽 끝과 맞닿는 최소의 오른쪽 끝을 구하면 어떨까? 란 생각을 했었다. 위의 예시 위주로 생각해낸 방법이였고, 혹시나 하는 마음에 구현을 시도했었다. 하지만, 역시 이 아이디어는 아니였다.

 

그 다음, [0, M]을 덮는 선분 중 가잔 많은 곳을 덮는 선분을 우선적으로 고르는 것이 어떨까? 란 생각도 했었다.

하지만, 구현을 어떻게 해야할지가 문제였고, 무엇보다, 반례가 떠올랐다.

 

10

0 3

3 10

1 9

0 0

답: 2

오답: 3

 

그러면, 좌표를 기준으로 생각해서, 특정 좌표를 덮는 선분의 갯수가 가장 적은 선분을 먼저 고르면 어떨까? 란 생각을 했다. 하지만, 갯수가 중복되었을 경우 어떻게 처리해야할지가 문제였고, 역시 직감이였기에, 이 아이디어도 구현 도중 포기했다.

 

정답

여러 생각이 혼잡되었을 때, 나는 머리를 식히고, 처음부터 고민을 하기 시작했다. 우선 다시 왼쪽 끝을 기준으로 sort한 선분을 순서대로 맞이한다. 좌표가 0을 포함한 선분들을 생각했을 때 어떤 선분을 고르는 것이 이득일까?

[0, M]을 덮는 최대한의 선분이다.

 

여기까지 생각했을 때, 맨 위의 예시를 떠올렸다.

일단 0과 유일하게 겹치는 선분(-1, 5)은 무조건 포함을 해야한다.

이 다음 (3 7), (4 10) 중 하나를 골라야한다. 이 중 골라야하는 것은 (4, 10) 선분이다. 어째서? 좌표 5를 포함한 좌표 중

5 이상의 구간을 가장 많이 덮기 때문이다. 이미 5 이하의 구간은 덮어져있어서 무시 할 수 있다.

 

그러자 하나의 아이디어가 떠올랐다.

1. 우선 좌표 0을 포함한 선분 중 가장 큰 오른쪽 끝을 구한다. 이를 r1이라 하자.

2. 좌표 r1을 포함한 선분 중 가장 큰 오른쪽 끝을 구한다. 이를 r2라 하자.

3. 좌표 r2를 포함한 선분 중 가장 큰 오른쪽 끝을 구한다. 이를 r3라 하자.

....

선분은 최대한 덮는 것이 최소한의 선분을 구할 수 있다는 그리디적인 발상이다!

주의할 점은, 마지막 선분도 고를 수 있도록, 마지막에 sort 되는 더미 선분을 추가적으로 넣고

마지막에, 선분의 끝이 M을 넘는지 체크하자.

그렇게 나온 코드는 다음과 같다.

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

priority_queue<int> pq;
vector<pair<int, int>> line;
int L, R, M, ans = 0;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> M;
	while (true)
	{
		cin >> L >> R;
		if (L == 0 && R == 0) break;
		if (R < 0 || L > M) continue;
		line.push_back({L, R});
	}
	line.push_back({ M, 50001 });
	sort(line.begin(), line.end());
	int l = 0, r = 0;
	for (int i = 0; i < line.size(); i++)
	{
		if (line[i].first > l)
		{
			if (line[i].first > r)
			{
				ans = 0;
				break;
			}
			else
			{
				l = r;
				r = line[i].second;
				++ans;
			}
		}
		else
			r = max(r, line[i].second);
	}
	if (r < M) ans = 0;
	cout << ans << '\n';
}

스위핑과 그리디적인 발상이 섞인 재밌는 문제였다.