BOJ 13334 철로 풀이

문제 링크

 

스터디를 하게 되면서 매주 정해진 BOJ 문제를 풀고, 풀이를 작성하게 되었다.

문제에는 철로, 사람의 집, 사람의 사무실이라고 되어있지만, 사실 간단하게 생각해보면 다음과 같은 내용이다.

 

f(x) = [a_i, b_i] ⊆ [x, x+d] 인 i의 갯수 (단, a_i ≤ b_i) 

 

이 f의 최대값은 얼마인가? 라고 물어보는 문제다.

 

그럼 문제의 이슈는 크게 두 가지로 좁혀진다.

 

1. 어떠한 x에 대해서 해 볼 것인가?

 

임의의 x를 골라보자.

 

[a_i, b_i] ⊆ [x, x+d]를 만족하는 i가 존재한다면

그 i들 중, a_i가 가장 작은 i가 존재한다.

 

그 i를 k라 하자.

 

이제 f(a_k) ≥ f(x) 임을 보이자.

 

[a_i, b_i] ⊆ [x, x+d]를 만족하는 i들에 대해

 

a_i ≥ a_k, b_i ≤ x+d 가 성립한다.

 

그런데 a_k ≥ x 이므로,

 

b_i ≤ x+d 이면, b_i ≤ a_k+d가 된다.

 

따라서, a_i ≥ a_k, b_i ≤ a_k+d.

 

[a_i, b_i] 는 [a_k, a_k+d]에 포함된다.

 

따라서, f(a_k) ≥ f(x)

 

[a_i, b_i] ⊆ [x, x+d] 를 만족하는 i가 존재하지 않으면, f(x) = 0 이므로,

 

이 경우엔, 모든 a_i에 대해 f(a_i) ≥ f(x) 이다.

 

두 경우를 종합하였을 때,

 

어떠한 f(x)에 대해서도 그 f(x) 이상인 f(a_i)가 존재한다.

 

따라서 모든 a_i에 대해 f(a_i)를 구한다면, 그 f(a_i) 들 중 최대값이 문제에서 구하고자 하는 답이다.

 

2. 어떻게 f(x)를 계산할 것인가?

 

[a_i, b_i] ⊆ [x, x+d] 를 생각해보면,

 

a_i ≥ x 를 만족하는 i의 집합과,

 

b_i ≤ x+d 를 만족하는 i의 집합의 교집합이다.

 

 

라 하면, f(x) = n(A∩B) 이다.

 

중학생 때 배운 집합을 떠올려보면

 

n(A∪B) = n(A) + n(B) - n(A∩B)

 

라는 식이 있던 걸 기억할 것이다.

 

이 식을 수정해보면,

 

n(A∩B) = n(A) + n(B) - n(A∪B)

 

가 된다.

 

a_i와 b_i를 미리 정렬해 놓으면, n(A)와 n(B)를 구하는 각각의 시간복잡도는 log N 이다.

 

이제, n(A∪B) 를 구하는 것을 생각해보자.

 

AUB는 전체 집합에서 (AUB)의 여집합을 뺀 것과 같다.

 

드 모르간의 법칙에 의하면, (AUB)의 여집합은, A의 여집합과 B의 여집합의 교집합이다.

 

 

그런데, a_i < x, b_i > x + d 두 부등식에 의해,

 

b_i-a_i > x+d-x

 

b_i - a_i > d

 

를 얻을 수 있다. 즉, A의 여집합과 B의 여집합의 교집합에 속하는 원소는 b_i - a_i > d 의 속성을 가진다는 것이다.

 

각, a_i와 b_i를 입력 받고, d 또한 입력 받으므로

 

우리는 실제로 시행되는 a_i와 b_i에 대해, b_i - a_i > d를 만족하는 i들을 애초에 전체 집합에 넣지 않음으로써,

 

전체 집합에 속하는 모든 i들에 대해 b_i - a_i <= d를 만족하게 만들 수 있다.

 

그렇게 한다면, A의 여집합과 B의 여집합의 교집합에 속하는 원소는 0 개가 된다.

 

그리고 전체 집합에 속하는 i의 갯수도 간단하게 알 수 있다.

 

따라서 이 2번 과정에선 log N 만큼의 시간복잡도가 소요된다.

 

따라서, 1, 2번에 의해 총 시간복잡도는 O(NlogN) 이다.