[BOJ] 1300 : K번째 수 - travelbeeee

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

---

이분탐색

 N x N 행렬의 i 번 째 행을 보면 i번 째 구구단인 것을 알 수 있습니다. 따라서, i번 째 행에서 어떤 값 x 보다 작거나 같은 수는 x / i 를 통해 구할 수 있습니다. 주의할 점은 예를 들어 N이 5이면 3번 째 행은 3 6 9 12 15 가 된다. 이때 18보다 작거나 같은 수를 18 / 3 으로 구해버리면 하나가 더 카운트 된다. 즉 i번 째 행에서 얻을 수 있는 갯수는 최대 N개 이므로 i번 째 행에서 x 보다 작거나 같은 수는 min( x / i , N ) 으로 구할 수 있다.

 

따라서, 다음과 같은 식을 만들 수 있다.

F(x) := N x N 행렬에서 x 보다 작거나 같은 숫자의 갯수

       := 1 ~ N 까지의 수로 x 를 나눈 값과 N 중 더 작은 값을 다 더한다.

 

이때, 정의상 F(x) 는 단조증가함수가 되므로 이분탐색을 이용할 수 있다.

#include<iostream>
#include<algorithm>

using namespace std; 

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int N, K;
	cin >> N >> K;

	int result = 0;
	int left = 1, right = K;
	while (left <= right) {
		int mid = (left + right) / 2;
		int cnt = 0;
		for (int i = 1; i <= N; i++) { // cnt에는 mid보다 작거나 같은 애들 담김.
			cnt += min(mid / i, N);
		}
		 if (cnt < K) // mid로는 아직 부족함.
			left = mid + 1;
		else{ // mid로 충분할 수도 있고, 더 작아질 수도 있으므로 일단 저장.
			result = mid;
			right = mid - 1;
		 }
	}
	cout << result << '\n';
	return 0;
}

---