[BOJ #2110] 공유기 설치

BOJ #2110, 공유기 설치 문제입니다.

이전에 풀어서 맞은 문제였는데 얼마 전 재채점이 되면서 틀렸길래 다시 풀어보면서 글을 작성하기로 했습니다.

접근

가장 인접한 두 공유기 사이의 거리가 최대가 되도록 하는 '배치'를 찾는 것은 상당히 어려워 보입니다. 모든 배치를 다 검토해 보는 것은 2 <= N <= 200000, 2 <= C <= N이므로 시간이 너무 오래 걸립니다. 따라서 바로 max(가장 인접한 두 공유기 사이의 거리)를 찾기로 했습니다.

 

알고리즘 문제를 풀 때 문제 내의 요소를 활용하여 기본적으로 단조 함수를 만들 수 있다면 큰 도움이 됩니다. 이분 탐색을 활용할 수 있기 때문입니다. 여기서도 단조 감소하는 여러 가지 함수를 만들어 볼 수 있었습니다.

• 함수 a(x): x개의 공유기를 설치했을 때 max(가장 인접한 두 공유기 사이의 거리) -> 기본적으로 단조 감소 함수입니다. 2개를 설치하는 경우보다 3개를 설치하는 경우가, 3개를 설치하는 경우가 4개를 설치하는 경우보다 큰 함숫값을 가지는 것은 자명합니다.
• 함수 b(x): 가장 인접한 두 공유기 사이의 거리를 x 이상으로 배치할 수 있을까? (답변이 예일 시 1, 아니오일 시 0) -> 기본적으로 단조 감소 함수입니다. 'x 이상'이라는 워딩 때문입니다. b(k) = 1이면 k보다 작은 모든 자연수 n에 대해 b(n) = 1임이 보장됩니다. 즉 어떤 testcase의 솔루션 s에 대해서 그래프는 다음과 같은 모양을 띠게 됩니다.

  

  함수 b(x)의 그래프

함수를 더 만드려면 더 만들 수 있겠지만, 일단 우리가 주목해야 할 함수는 b(x)입니다.

왜 a(x)는 안 되고 b(x)는 되는가

문제를 이분 탐색으로 풀기 위해 함수를 만들 때 신경 쓸 점이 더 있습니다.

1. 첫 번째는 함숫값을 구하는 것과 문제의 답을 구하는 것이 동일하면 안 됩니다. 언뜻보면 당연한 이야기지만 이분 탐색을 활용해 보겠다고 여러가지 함수를 찾는 과정에서 이런 실수를 할 가능성이 있습니다. 가령 a(x)의 경우 a(C)가 문제의 답이기 때문에 이분 탐색을 하는 것이 의미가 없습니다. 이분 탐색은 함숫값을 찾는 과정이 아니라, 조건을 만족하는 함숫값을 가지는 x값을 찾는 과정입니다.
2. 두 번째는 함숫값을 구하는 것이 시간 내에 충분해야 합니다. 이분 탐색은 기본적으로 O(logN)의 시간복잡도를 가지고 있고 따라서 함숫값을 구하는 과정의 시간복잡도가 O(A)라고 하면 해당 알고리즘의 시간복잡도는 O(AlogN)이 됩니다. 만약 A의 시간복잡도가 너무 크면 이분 탐색을 하더라도 시간 초과가 나게 됩니다.

이런 맥락에서, b(x)가 조건에 맞는 함수라고 하면 O(A)를 검토해보아야 합니다. O(N) 정도면 전체가 O(NlogN)으로 충분할 것입니다.

b(x)의 함숫값 구하기 전략

b(x)를 충분한 시간복잡도 내에서 구해 봅시다. 가장 처음으로 제가 떠올린 전략은 다음과 같습니다.

'첫 번째 집에는 무조건 공유기를 설치하고 x 이상 떨어져 있는 가장 가까운 거리의 집에 공유기를 놓으면서 C개까지 놓을 수 있는지 확인한다. C개까지 놓을 수 있다면 1을 반환하고 그렇지 않다면 0을 반환한다.'

시간복잡도 또한 O(N)으로 충분하다는 것을 알 수 있습니다.

b(x)의 함숫값 구하기 전략 - 증명

이제 이 전략을 검토해 보겠습니다. 우리가 경계해야 할 것은 가능한데 불가능하다고 판단하는 경우, 불가능한데 가능하다고 판단하는 경우 두 가지입니다.

 

우선 후자는 현재 생각한 전략대로 가면 쉽게 문제가 없다고 판단할 수 있습니다. 문제가 되는 것은 전자인데, 즉 현재 전략을 따랐을 때 불가능한 testcase가 '다른 전략'을 따랐을 때 가능한 경우가 있냐는 것입니다. 저는 다음과 같은 사고과정을 근거로 없다고 결론지었습니다.

• x 이상 떨어진 집들 중에서 다음 공유기의 위치를 정하는 것은 모든 전략에서 따라야 할 법칙이다.
• 현재 전략은 x 이상 떨어진 집들 중에서 가장 가까운 집을 택하는 것이므로 '다른 전략'은 그렇지 않은 집을 택하는 것이다.
• 가장 가까운 집을 택했을 때(현재 전략) 그 다음에 택할 집을 p, 그렇지 않은 집을 택했을 때(다른 전략) 그 다음에 택할 집을 q라고 하면 p의 좌표 <= q의 좌표이다. (p의 좌표 == q의 좌표인 경우 p == q)
• 계속 진행하다 보면 p == q가 되는 시점이 생기는 경우로 끝나거나, p는 존재하고 q는 존재하지 않는 경우로 끝난다. 따라서 현재 전략에서 안 되면 다른 전략에서도 안 된다.

구현

우리가 구현해야 할 것은 두 가지입니다. 위 함수 b(x)의 그래프 그림에서 s를 찾는 부분(main)과 b(x)만 구현하면 되겠습니다. 먼저 main 함수입니다.

int main(void) {
	cin >> N >> C;
	for (int i = 0; i < N; i++) cin >> x[i];
	sort(x, x + N);

	int l = 1, r = x[N - 1], mid;
	do {
		mid = (l + r) / 2;
		if (!b(mid)) r = mid;
		else l = mid + 1;
	} while (l != mid);
	cout << l - 1 << endl;

	return 0;
}

단조 함수에서 이분 탐색을 하려면 upper bound와 lower bound라는 개념을 이용해야 하는데 그것을 학습하거나 검색해서 사용하기보단 직접 짜 보시는 것을 추천드립니다. 크게 어렵지 않고 위 코드는 제가 이 문제에 맞춰서 간단하게 구현해본 것입니다. 다음은 b(x)인데 집의 좌표를 담은 배열을 x로 썼기에 bool b(int d);로 정의했습니다.

bool b(int d) {
	int curr = x[0], cnt = 1;
	for (int i = 1; i < N; i++) {
		if (x[i] - curr >= d) {
			cnt++;
			curr = x[i];
		}
	}
	return cnt >= C;
}

매우 간단한 코드로 이 문제를 해결할 수 있습니다.