글 읽기 - 왜 mid를 정하는 건가요?

d252b 6년 전 0

이분 탐색 이므로 중간값으로 비교해서

start = mid+1 혹은 end= mid -1 로 하는 것은 자명한데요.

궁금한 점은

집이

1 2 4 8 9 로 주어질 때

그 이분탐색하는 기준점(mid)가 왜 (1+9)/2 가 되어야 하나요?

현재 우리는 공유기가 설치되는 '거리' 의 최댓값을 찾고 있는 것인데

그 공유기간 거리의 최댓값과 주어진 집 사이의 거리에서의 중간값과 관련이 있나요?

* 저는 아래 코드처럼 작성하였으나 시간초과가 떴습니다.

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

using namespace std;
vector<int> arr;
int n, c;
int cnt = 1;
int sol = 0;
int main()
{
	scanf("%d %d", &n, &c);
	arr.resize(n + 1, 0);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &arr[i]);
	}

	sort(arr.begin() + 1, arr.end());

	for (int i = 1;; i++)        // 공유기 간 거리
	{
		cnt = 1;
		for (int j = 1; j < n; j++)    
		{
			if (arr[j] + i <= arr[j + 1])   
				cnt++;
		}
		if (cnt < c)
		{
			sol = i;
			break;
		}
	}
	printf("%d", sol);
}

chogahui05 6년 전 0

중간값을 기준으로 반씩 나눠서 탐색하기 때문입니다.

예를 들어서

1 2 2 3 4 4 4 7 8 9 가 있다고 칩시다.

여기서 5보다 큰 최초의 위치를 찾는다고 해 볼까요?

mid는 4이므로

1 2 2 3 [4] 4 4 7 8 9 일 겁니다.

여기서 4는 5보다는 작잖아요.

그러니까 우측 구간에서 찾겠죠. 이렇게 이분탐색은 반씩 줄여가면서 찾습니다.

chogahui05 6년 전 0

여기서는 f(x)를 x의 간격으로 공유기를 놓았을 때

설치해야 하는 공유기의 갯수 정도로 보시면 되겠네요. 만약에 간격 x가 작아진다면 f(x)가 커지거나 같아질 게 자명하고요.

x가 커지면 f(x)가 작아지거나 같을 게 자명하네요.

d252b 6년 전 0

1 2 2 3 4 4 4 7 8 9 가 있다고 칩시다.

여기서 5보다 큰 최초의 위치를 찾는다고 해 볼까요?

이 부분에서 5, 즉 (1+9)/2 =5 이것이 공유기 간 거리를 나타내는 건가요??

chogahui05 6년 전 0

그렇게 이해하시면 더 헷갈리실 겁니다.

일단 f(x)를 요래 정해봅시다.

공유기간의 거리 중 최소 거리가 x 이상이여야 할 때 공유기 몇 개를 설치할 수 있을까?

1 2 4 8 9

에서 만약에 x가 4라면 이렇게 설치해야 합니다.

(1) 2 4 (8) 9

1 다음에 4에다가 설치하면 곤란하겠죠?

x가 3이라면 이렇게 설치할 수 있겠죠.

(1) 2 (4) (8) 9

x가 2라면 이렇게 설치 가능합니다.

(1) 2 (4) (8) 9

결국 이 f(x)가 감소, 또는 증가 함수네요. 이분 탐색 적용 가능하겠지요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 mid를 정하는 건가요?

d252b 6년 전 0

chogahui05 6년 전 0

chogahui05 6년 전 0

d252b 6년 전 0

chogahui05 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말