이진 탐색 응용 문제 - 2

이 문제는 이진 탐색을 떠올려 풀기 어려운 문제이다.

이진 탐색으로 중앙값보다 작은 수의 개수를 세면서 범위를 줄이는 방법으로 문제를 해결한다.

 

백준 - 1300: 배열에서 k번째 수 찾기

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

1300번: K번째 수

 

코드

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

static vector <int> num;
// static vector <int> num_f;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long n, m;
	long answer = 0;

	cin >> n >> m;

	long s = 1, e = m;

	while (s <= e) {

		long mid = (s + e) / 2;
		long cnt = 0;

		// 중앙값보다 작은 수는 몇 개인지 계산
		for (int i = 1; i <= n; i++) {
			cnt += min(mid / i, n); // 작은 수 세기
		}

		if (cnt < m) { // mid값보다 작은 수가 m보다 작으면 시작 인덱스는 mid+1
			s = mid + 1;
		}
		else { // mid값보다 큰 수가 m보다 크면 종료 인덱스는 mid-1, 정답 변수는 중앙값
			answer = mid; // 현재 단계의 중앙값을 정답 변수에 저장
			e = mid - 1;
		}
	}
	cout << answer;
}