[G4] 백준 8983번 사냥꾼 C++ 이분 탐색

리뷰

 

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

이분 탐색을 통해 잡을 수 있는 동물의 수를 O(LogN)에 구하는 문제

 

전역 변수

• m : 사대의 개수를 저장할 변수
• n : 동물의 수를 저장할 변수
• l : 사정거리를 저장할 변수
• ans : 정답을 저장할 변수
• lst : 사대의 위치 정보를 저장할 배열

 

함수

없음

 

 

문제풀이

1. m, n, l의 값을 각각 입력 받고, m개의 사대의 개수를 lst배열에 입력 받아준다.
2. sort 함수를 통해 lst배열을 오름차순으로 정렬한다.
3. n번의 while루프를 수행하고 매 루프마다 x, y좌표를 입력 받아준다.
4. L을 0으로, R을 m - 1로 초기화 하고, L이 R 이하일 경우 while루프를 수행해 준다.
5. 매 루프마다 변수 MID에 L + R을 2로 나눈 몫을 저장해 준다.
6. 변수 dist에 lst배열의 MID인덱스 값 - x의 절대값에 y를 더해준 값을 저장해 준다.
7. dist가 사정거리 이하라면 ans를 증가시킨 후 break처리해 준다.
8. 아니라면 x가 lst[MID]보다 클 경우 오른쪽으로, 작을 경우 왼쪽으로, 같다면 break처리해 준다.
9. 모든 탐색이 종료된 후 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 동물의 x좌표와 사대의 x좌표가 동일한데 사정거리에 들지 못하는 경우 바로 break처리해 주면 된다.

 

정답 코드

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

int m, n, l, ans;
int lst[100000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> m >> n >> l;
	for (int i = 0; i < m; ++i) cin >> lst[i];
	sort(lst, lst + m);

	while (n--) {
		int x, y; cin >> x >> y;
		int L = 0, R = m - 1;
		while (L <= R) {
			int MID = (L + R) / 2;
			int dist = abs(lst[MID] - x) + y;
			if (dist <= l) {
				ans++;
				break;
			}
			else {
				if (x > lst[MID]) L = MID + 1;
				else if (x < lst[MID]) R = MID - 1;
				else break;
			}
		}
	}
	cout << ans;
}