백준/1300번/K번째 수/골드2

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

문제 설명

Site: Baekjoon
Number: 1300
Category: 매개변수 탐색
Rank: Gold 2

주어진 2차원 배열을 오름차순으로 정렬하였을 때 K번째에 오는 숫자를 찾아 출력하는 문제이다.

N의 범위가 너무 크기 때문에 N x N크기의 배열을 만들려고 한다면 메모리 초과가 발생하며, 완전 탐색으로 진행하게 되면 시간 초과가 발생한다.

매개 변수 탐색을 통해 거꾸로 생각하여 어떤 수가 주어졌을 때, 해당 수가 K번째에 오는지를 통해 해결하면 된다.

현재 탐색 중 수가 9라고 한다면, 9보다 작은 수가 몇개가 있는지 모든 열 또는 행을 지나가며 계산하면 된다.

각 행에서 나올 수 있는 9보다 작은 수는 i번째 행 또는 열에서 9/i개 또는 9개가 나오며, 이 둘중 더 작은 값이 해당 행에 9보다 작은 수의 갯수이다.

이 문제는 FalseeeeeeeeeTrueeeeee 문제이기 때문에, low를 범위에서 제한하고 high를 범위에 포함하는 방식을 통해 해결하였다.

#include <iostream>

using namespace std;

long long Count(long long mid, long long N)
{
	long long cnt = 0;
	for(long long i = 1; i <= N; i++)
	{
		cnt += min(mid/i, N);
	}

	return cnt;
}

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

	long long N, K;
	cin >> N >> K;

	K = min((long long)1000000000, K);

	//low는 정답에 포함되지 않고, high는 정답에 포함한
	long long low = 0, high = N*N;

	while(low +1 < high)
	{
		long long mid = (low + high) / 2;

		//mid보다 작은 수의 갯수가 K보다 작은 경우, mid는 답이 될 수 없다 -> 범위 밖인 low = mid
		if (Count(mid, N) < K)
			low = mid;
		else
		//mid보다 작은 수의 갯수가 K보다 큰 경우, mid는 답이 될 수 있다 -> 범위 안인 high = mid
			high = mid;
	}

	//FalseeeeeTrueeee의 True경계선에 있는 high를 출력한다.
	cout << high;

	return 0;
}