[BOJ]1300번: K번째 수 (c++)

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

1300번: K번째 수

 

이분탐색

#include <iostream>
#include <algorithm>

using namespace std;

// 두 수의 곱이 int범위를 넘을 수 있기 때문에 long long 형으로 선언
long long N, K;

// num보다 더 작은 수의 개수 구하기
long long count_smaller(long long num)
{
	// 두 수가 [1, N] 범위에 있을 동안 반복문
	long long cnt = 0;
	for (long long i = 1, j = N; i <= N && j > 0; ++i)
	{
		// 두 수이 곱이 num보다 크면 --j
		while (i * j >= num)
		{
			--j;
		}

		if (j > 0)
		{
			cnt += j;
		}
	}

	return cnt;
}

// 이분탐색으로 K번째 수 구하기
long long binary_search(long long left, long long right)
{
	long long ans = 0;
	while (left <= right)
	{
		long long mid = (left + right) / 2;

		// mid보다 더 작은 수의 개수가 K보다 작으면 
		if (count_smaller(mid) < K)
		{
			ans = mid;
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}

	}
	return ans;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	cin >> N >> K;

	// 이분탐색으로 K번째 수 구하기
	cout << binary_search(0, N * N);


	return 0;
}

 

수 이어쓰기 2 문제와 매우 유사하다

 

크기가 N×N인 배열 A에 들어있는 수 A[i][j] = i×j 이다.
이 수를 일차원 배열 B에 넣고 오름차순 정렬했을 때, B[k]를 구해보자.
인덱스는 1부터 시작한다.

첫째 줄에 배열의 크기 N이 주어진다. N은 10^5보다 작거나 같은 자연수이다.

 

수의 크기가 너무 크기 때문에

실제 배열을 만들고 정렬을 할 수가 없다.

따라서 K번째의 수를 이분탐색을 통해 찾아야 한다. 

 

탐색 기준은 mid보다 작은 수의 개수를 세어, 그 수가 K보다 작은지 확인하는 것이다.

이때 배열의 인덱스의 범위는 [1, 10^5]이므로 두 인덱스를 곱한다면 int의 범위를 넘어버리게 된다.

따라서 자료형을 long long으로 선언해주어야 한다.