[백준/1300] K번째 수 (이분 탐색)

1. 문제

 

 

 

2. 접근 방법

이분 탐색으로 해결할 수 있는 적당한 난이도의 문제... 라고는 하나

접근 방법이 잘 떠오르지 않아 애를 먹었던 문제이다.

 

이 문제는 브루트 포스적인 방법으로 접근하면, O(N * log N) 이라 시간 초과로 풀 수 없다.

그러므로 효율적인 계산 방법을 생각해야 하는데, 아래와 같이 구할 수 있음을 알게 되었다.

 

우선, N =5 일 때, 즉 5 X 5 배열을 통해서 계산을 생각해보자.

 

그리고 여기에서 k = 11 일 때, 즉 B[11] 을 찾는 경우를 생각해보자.

 

우리가 찾는 11번째의 숫자를 S 이라고 한다면, 다음과 같이 접근해야 한다.

 

"전체 숫자 중에서, S보다 작거나 같은 숫자의 개수가 11개보다 작으면 안된다!"

→ 만약 그렇다면, 찾는 숫자의 범위를 큰 쪽으로 옮겨야 한다.

 

그렇다면, S보다 작거나 같은 숫자의 개수는 어떻게 구할까?

이 계산을 구현하는 것이 이 알고리즘의 핵심이 되겠다.

 

만약 S를 5라고 가정하고, 5보다 작거나 같은 개수를 찾는 경우를 생각해보자.

 

5보다 작거나 같은 개수를 구하려면, 각 행에서 조건에 맞는 값을 구한 뒤 합하면 된다.

즉, 이 배열에서 5보다 작거나 같은 개수의 합은 10개이다.

 

그렇다면 S를 8이라고 가정해보자.

 

여기에서는 14이다.

 

잘 생각해보면, 각 행에서의 S보다 작거나 같은 숫자의 개수는

min(S / i, N) 임을 알 수 있다.

왜냐하면, 각 행은

i * 1,   i * 2,   i * 3,   i * 4,   .....   , i * j 이기 때문에,

S를 i로 나눈 값에 나머지를 버린 값이 그 행에서 S보다 작거나 같은 개수가 되기 때문이다.

 

그러므로, 우리는 S를 찾기 위해

초기값 = 1,   마지막 값 = k,   중간 값 = (1 + k) / 2

로 시작하는 이분 탐색을 적용하면 된다.

여기에서 마지막 값이 k인 이유는

"B[k] 의 값은 k보다 작거나 같기" 때문이다.

 

 

 

3. 구현

#include <iostream>
#include <algorithm>

using namespace std;

int N, k;

int main(void)
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> k;

	int f = 1, l = k, m;
	int res = 0;

	for (;;)
	{
		if (f > l) break;
		m = (f + l) / 2;

		int cnt = 0;
		for (int i = 1; i <= N; i++)
		{
			cnt += min(N, m / i);
		}

		if (cnt >= k)
		{
			res = m;
			l = m - 1;
		}
		else
		{
			f = m + 1;
		}
	}

	cout << res << '\n';

	return 0;
}