백준 8983번
https://www.acmicpc.net/problem/8983

문제

---

생각하기

---

• 이분 탐색 문제이다.
  • 동물을 잡을 수 있는 사대의 위치를 이분탐색으로 찾아낸다.

동작

    var ans = 0
    for(i in 0 until N) {
        StringTokenizer(br.readLine()).run {
            val x = nextToken().toInt()
            val y = nextToken().toInt()

            if (y > L) return@run
            val lower = x - (L - y)
            val upper = x + (L - y)

            if (binarySearch(lower, upper, 0, M - 1)) ans++
        }
    }

값을 입력받으면서 L인 사거리와 직접적으로 영향을 받는 y가 L보다 크면 어차피 잡지 못하는 동물이므로 continue 한다.

그리고 x를 기준으로 왼쪽이 lower가 되고, 오른쪽 기준으로 upper가 된다.

이렇게 범위가 설정되고 나서 이분 탐색으로 어떤 사대에서 해당 위치의 동물을 잡을 수 있는지를 찾아낸다.

private fun binarySearch(lower: Int, upper: Int, left: Int, right: Int): Boolean {
    if (left > right) return false

    val mid = (left + right) / 2
    if (sandCoors[mid] in lower..upper) {
        return true
    }

    if (sandCoors[mid] < lower) {
        return binarySearch(lower, upper, mid + 1, right)
    } else {
        return binarySearch(lower, upper, left, mid - 1)
    }
} // End of binarySearch()

left와 right가 low, high 가 되어 범위를 탐색한다.

sands[mid]가 lower와 upper의 사이 범위에 들어오게 될 경우 true를 return 하게 된다.

그리고 재귀로 빠져나오면서 ans가 증가하게 되면서 답을 찾을 수 있게 된다.

결과

코드

---

Kotlin

import java.io.*
import java.util.*

// input
private lateinit var br: BufferedReader

// variables
private var M = 0
private var N = 0
private var L = 0
private lateinit var sandCoors: IntArray


fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    var ans = 0
    for(i in 0 until N) {
        StringTokenizer(br.readLine()).run {
            val x = nextToken().toInt()
            val y = nextToken().toInt()

            if (y > L) return@run
            val lower = x - (L - y)
            val upper = x + (L - y)

            if (binarySearch(lower, upper, 0, M - 1)) ans++
        }
    }

    sb.append(ans)
    return sb.toString()
} // End of solve()

private fun binarySearch(lower: Int, upper: Int, left: Int, right: Int): Boolean {
    if (left > right) return false

    val mid = (left + right) / 2
    if (sandCoors[mid] in lower..upper) {
        return true
    }

    if (sandCoors[mid] < lower) {
        return binarySearch(lower, upper, mid + 1, right)
    } else {
        return binarySearch(lower, upper, left, mid - 1)
    }
} // End of binarySearch()

private fun input() {
    StringTokenizer(br.readLine()).run {
        M = nextToken().toInt() // 사대의 수
        N = nextToken().toInt() // 동물의 수
        L = nextToken().toInt() // 사정거리
    }

    StringTokenizer(br.readLine()).run {
        sandCoors = IntArray(M) {
            nextToken().toInt()
        }
    }
    sandCoors.sort()
} // End of input()