[C++] 백준 1300. K번째 수

🌽 문제

🥕 입출력

🥔 풀이

핵심은 이분 탐색 시 mid 값보다 작은 수의 개수를 구하도록 하는 것이다.
이 때 mid 값보다 작은 수의 개수를 구하는 방법은,
각 행을 돌며 mid / i 값과 각 행의 최대 개수인 N을 비교하는 것이다.
행 방향 값들은 모두 정렬되어 있기 때문에 이 방법을 사용할 수 있는 것이다.

예를 들어 4*4 행렬은 아래와 같다.

1  2  3  4
2  4  6  8
3  6  9  12
4  8  12 16

만약 mid가 3이라면, 1행에서 3보다 작은 값은
1*1, 1*2, 1*3. 즉, 3/1개와 같다.
2행에서 3보다 작은 값은 3/2=1개이고,
..
4행에서 3보다 작은 값은 3/4=0개이다.

이렇게 구한 모든 개수를 더하면 mid인 3보다 작은 원소의 개수를 구할 수 있다.
총 개수가 K보다 작을 때와 그렇지 않을 때로 구분하여 계산하면 된다.

🥬 코드

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

long long N, K, ans;

void solution() {
	long long l = 1;
	long long r = N * N;
	long long m, cnt;
	while (l <= r) {
		m = (l + r) / 2;
		cnt = 0;
		for (long long i = 1; i <= N; i++)
			cnt += min(m / i, N);
		if (cnt < K) {
			l = m + 1;
		}
		else {
			ans = m;
			r = m - 1;
		}
	}
	return;
}

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

	cin >> N >> K;
	solution();
	cout << ans;

	return 0;
}

🥜 채점