백준 1300번(Gold 1)

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

이진 탐색을 이용하면 간단하지만 그 떠올리는 과정이 상당히 힘들었었던 문제이다.

#include <iostream>

using namespace std;


int main() {
	cin.tie(0)->sync_with_stdio(false);
	int N; long long K;
	cin >> N >> K;
	//B[k] K보다 작거나 같은 수가 적어도 K개 있다.

	long long start = 1;
	long long end = K;
	long long ans = 0;
	while (start <= end) {
		long long mid = (start + end) / 2;
		long long count = 0;
		for (int i = 1; i <= N; ++i) {
			if ((mid / i) > N) {
				count += N;
			}
			else {
				count += (mid / i);
			}
		}

		if (count < K) {
			start = mid + 1;
		}
		else {
			ans = mid;
			end = mid - 1;
		}
	}

	std::cout << ans << '\n';
	return 0;
}

a[N][N] 을 b[N^2]으로 1차원 배열로 치환하고 그 배열의 값들을 오름차순으로 정렬했을 때, k번쨰 값을 출력해야하는데,

떠올려야 하는 아이디어는 b[k] = T 에서 T보다 작거나 같은 값들이 적어도 k개 있다는거다.

k번째 값이 T일 것이고, k+n값도 T일 수 있다.

또한, k번째 값은 k보다 작거나 같은 값이여야 한다는 것을 알아야한다.