백준 1300번 K번째 수 (C++)

이분탐색에 조짐 당하는 두번째 날이다.
근데 오늘은 이 문제를 통해 많이 얻어가는 거 같다.

문제링크

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

설명

저번 공유기 설치 문제에서도 언급했듯이, 이번 문제에서도 무엇을 기준으로 잡고 범위를 줄여나갈 지 고민하였다.
index와 value 둘 중 고민하였는데 나는 index를 활용하려다가 실패했다.
근데 생각해보니까 기준 잡을 게 index랑 value 밖에 없는 게 당연한 거 같기도 하고...
30분 정도 머리 싸매고 노트만 끄적이다가 질문글로 다시 행했다.

https://www.acmicpc.net/board/view/14272
https://sarah950716.tistory.com/16

위 질문글을 보고 문제를 풀 수 있었는데 저번 공유기 설치와 이번 문제의 공통점은 파라메트릭 서치라는 개념을 활용한다는 것이다.
자세한 내용은 두번째 링크에 정말 상세하게 설명이 되어있는데, 핵심은 이분탐색에서 기준을 잡고 범위를 줄여나갈 때, mid가 정답이 될 수 있는 값인지 아닌지 쉽게 판별할 수 있어야 한다는 것인 거 같다.

위 문제에서는 O(n)의 시간복잡도로 mid가 정답이 아닌지 쉽게 판별할 수 있다.
cnt와 k가 같아도 정답이 아닐 수 있는 데, 그 이유는 다음과 같다.

1. 같은 수가 여러 번 나올 수 있음
2. 나오지 않는 수인데 cnt == k를 만족할 수 있음

또한 이 문제에서는 end를 k로 설정하는데 이는 k번째 수는 반드시 k보다 작거나 같기 때문이다. end를 k로 설정하지 않으면 다른 변수들을 long long으로 선언해야하는 불편함이 따른다.

이 아이디어도 떠올리기 힘들어서 더욱 난이도가 높아진 거 같다.

저번 공유기 설치 문제에서 부족했던 점을 오늘 이 문제를 통해 조금은 채울 수 있었다. 계속해서 이분탐색 문제를 풀려고 시도해보면서 지금까지 배운 내용을 활용하려고 노력해야겠다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
	int n, k, start = 1, end, mid, cnt, ans = 1000000001;
	cin >> n >> k;
	end = k;
	while (start <= end)
	{
		cnt = 0;
		mid = (start + end) / 2;
		for (int i = 1; ; i++)
		{
			if (mid < i || i > n)
				break;

			cnt += min(n, mid / i);
		}

		if (cnt >= k)                       
		{
			ans = min(ans, mid);
			end = mid - 1;
		}

		else if (cnt < k)
			start = mid + 1;
	}
	cout << ans;
	return 0;
}