[백준] 1300번 K번째 수 C++ 문제풀이

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

문제 풀이

처음 문제 풀이에서는 Symmetric 행렬의 특성이 뭐가 있나 고민해봤는데 딱히 결론이 나오지 않았다...

다른 분들의 블로그를 참고해보니 이분검색으로 Mid 보다 작은 숫자들의 수를 세어서 그 합이 K보다 크면 작은 쪽을, 그 합이 K보다 작으면 mid보다 큰쪽을 검색하는 식으로 진행하는 문제였다. 

 

소스 코드

#include <iostream>
using namespace std;

int main() {
	long long N, K;
	cin >> N >> K;

	long long max_idx = K;
	long long min_idx = 1;
	long long result = 0;
    
	while (min_idx <= max_idx) {
		int mid = (max_idx + min_idx) / 2;
		long long temp = 0;
		for (long long i = 1; i <= N; i++) {
			temp += min(mid / i, N);
		}
		if (temp >= K) {
			result = mid;
			max_idx = mid - 1;
		}
		else {
			min_idx = mid + 1;
		}
	}
    
	cout << result << '\n';
}