[TIL] 이진탐색 알고리즘 문제 풀기

K번째 수

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

const fs = require('fs')
const input = fs.readFileSync('dev/stdin').toString().trim().split('\n')

const [n, k] = input.map((x) => +x)

let min = 1
let max = k
let x

while (min <= max) {
	let mid = Math.floor((min + max) / 2)

	let cnt = 0
	for (let i = 1; i <= n; i++) {
		cnt += Math.min(Math.floor(mid / i), n)
	}

	if (cnt >= k) {
		x = mid
		max = mid - 1
	} else {
		min = mid + 1
	}
}

console.log(x)

간단 설명

예를 들어 n = 3일 때는 B = [1,2,2,3,3,4,6,6,9]와 같은 정렬된 수열이 생길 것이다. 이때 B[7] 값은 7번째 수인 6이 될 것이다.

이렇게 보면 간단한 문제지만 문제에서 주어지는 수의 범위가 매우 크기 때문에 수열을 만들어서 풀면 시간 초과가 난다. 따라서 다른 접근 방식을 사용해야 한다.

B[k] = x일 때, B에서 x보다 작거나 같은 원소의 수가 k보다 크거나 같다.
x를 변화시키면서 (이진탐색) 적합한 x 값을 찾는다.

x보다 작거나 같은 원소의 수를 찾는 방법은
i * j <= x
j <= x / i

참고: https://jaimemin.tistory.com/988