[BOJ] 8983번 : 사냥꾼(Go, Golang)

문제 링크 : 백준 8983번

[문제 접근]

완전탐색으로 풀면 O(NM)이라 시간초과가 발생한다.
사정거리 크기가 1 ~ 1,000,000,000인 것을 보고 대충 이분 탐색으로 풀 수 있겠다 라고 생각을 했는데 대체 어떻게 풀어야하는지 감이 잡히질않아서 다른 사람 풀이를 참고했다.

동물의 크기를 fix하고 사대의 수를 이분 탐색을 돌려 O(NlogM)으로 풀었다.

1. 사대의 위치를 나타내는 슬라이스인 arr을 오름차순으로 정렬해준다.
2. 동물의 위치(x, y)를 하나 받아서 arr 배열을 이분 탐색을 돌린다.
   • min = x - (l - y), max = x + (l - y) 라고 하자.
   • 동물을 잡을 수 있는 사대의 후보는 min ~ max이다.
   • 따라서 저 후보 구간에 사대가 존재하면 ans++ 후 break한다.
   • 사대가 min보다 작을 경우 더 큰 사대를 선택해야하므로 start = mid + 1해준다.
   • 사대가 max보다 클 경우 더 작은 사대를 선택해야하므로 end = mid - 1해준다.
3. 최종적으로 ans를 출력해주면 된다.

[소스 코드]

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

var (
	r             = bufio.NewReader(os.Stdin)
	w             = bufio.NewWriter(os.Stdout)
	m, n, l, x, y int
)

func main() {
	defer w.Flush()
	fmt.Fscan(r, &m, &n, &l)
	arr := make([]int, m)
	for i := 0; i < m; i++ {
		fmt.Fscan(r, &arr[i])
	}
	sort.Sort(sort.IntSlice(arr))
	ans := 0
	for i := 0; i < n; i++ {
		fmt.Fscan(r, &x, &y)
		min := x - (l - y)
		max := x + (l - y)
		start := 0
		end := len(arr) - 1
		for start <= end {
			mid := (start + end) / 2
			target := arr[mid]
			if min <= target && max >= target {
				ans++
				break
			} else if target < min {
				start = mid + 1
			} else {
				end = mid - 1
			}
		}
	}
	fmt.Fprintln(w, ans)
}