백준 1300 K번째 수 풀이

문제

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

&Title
1300번 - K번째 수

&Question
세준이는 N*N크기의 배열을 만들었다. (배열의 방 번호는 1부터 
시작한다.)그 배열을 A라고 했을 때, 배열에 들어가는 수는 A[i][j] 
= i*j 이다.세준이는 이 수를 일차원 배열 B에 넣으려고 
한다. 그렇게 되면, B의 크기는 N*N이 될 것이다. 그러고 
난 후에, B를 오름차순 정렬해서 k번째 원소를 구하려고 한다.N이 
주어졌을 때, k번째 원소를 구하는 프로그램을 작성하시오. 

&Input
첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 
작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, 
n2)보다 작거나 같은 자연수이다. 

&Output
k번째 원소를 출력한다. 

&Example
-input
3
7

-output
6

요약

• A[i][j] = i*j 인 n*n 배열이 있다.
• 일차원배열 B에 A배열 원소를 넣은후 오름차순으로 정렬하여 k번째 원소를 구하라
• int범위 이내 자연수이다. min(10^9, n^2)

접근

• i*j는 결론적으로 i의 배수인 행임을 의미한다.
• 줄을 세운다고하면 num/(1~n)의 합이 k번째가 될것이다.
• n=3이고 k=5 num=3 라고 하자, 3/1 + 3/2 + 3/3 = 5이다. 여기서 3/1은 1번째 줄에 1 2 3을 의미하고 3/2는 2번째 줄에 2를 의미하고 3/3은 3번째 줄에 3을 의미한다.

풀이

1. 이게 핵심이다. 각 행에서 k번째보다 순서상 뒤의 개수의 합을 구한다.

    for (int i = 1; i <= n; ++i)
            cnt += min(mid / i, n);
   

소스

#include <iostream>
#include <algorithm>
using namespace std;
int n, k;

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	cin >> k;

	int l = 1, r = k;

	while (l <= r) {
		long long int cnt = 0;
		int mid = (l + r) / 2;
		for (int i = 1; i <= n; ++i)
			cnt += min(mid / i, n);
		if (cnt < k)l = mid + 1;
		else r = mid - 1;
	}

	cout << l << endl;
	return 0;
}