백준 1300: k번째 수

문제 요약

크기가 N×N인 배열 A에서, 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

문제 분류

• 이분 탐색
• 매개 변수 탐색

문제 풀이

B[k]의 값은 B[k]보다 작은 값이 k개 있다는 것을 의미한다. 즉, B[k]의 값을 이진 탐색 해 나가면서 탐색하는 수보다 작은 수의 개수를 찾으면 된다.

예를 들어, 다음의 배열 A에서 n은 3, 찾는 값 mid가 6일 때, 6보다 작거나 같은 수의 개수, cnt를 구해보면.

i	1	2	3	cnt
1	1	2	3	3
2	2	4	6	3
3	3	6	9	2

이렇게 각 행 마다 cnt를 구한 뒤, 누적시키면 8이 된다.
즉, B[8] = 6이라 생각할 수 있다.

그렇다면 mid = 3일때는 어떨까?

i	1	2	3	cnt
1	1	2	3	3
2	2	4	6	1
3	3	6	9	1

이에, B[5] = 3이라고 볼 수 있다.

여기서 각 행을 i라고 했을때, cnt의 값은 min(mid / i, n)가 될 것이다.

mid보다 i * cnt가 더 커지도록 cnt++을 계속한 결과 값은 mid / i의 식으로 나타낼 수 있다.
또한, cnt는 n보다 클 수 없기 때문에 min()으로 최소값으로 설정해준다.

또한 이진 탐색의 최솟값은 1, 최대값은 k가 될 것이다. B[k]는 반드시 k보다 작거나 같기 때문이다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

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