[BOJ] 1300 : K번째 수

1300 : K번째 수

풀이

파라메트릭 서치 문제인지 모를 때는 숫자가 너무 커서 막막했다. 파라메트릭 서치 문제인지 알아볼 수 있는 능력을 길러야겠다.

코드

이분탐색(파라메트릭 서치)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

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

	int n, k;
	cin >> n >> k;

	long long start = k - 1;
	long long left = 1, right = 1LL * n * n;
	//start보다 작거나 같은 숫자 개수(sum)를 센다.
	//sum>=k면 정답을 임시저장하고 right=start-1, sum<k면 left=start+1
	long long result = -1;
	while (left <= right) {
		//숫자세기
		long long sum = 0;

        //아래코드 다음과 같이 짧게써도 가능
        //for(int i=1;i<=n;i++) sum+= min(start/i,(long long)n);

		for (int i = 1; i <= min(start, (long long)n); i++) {
			for (int j = 1; j <= min(start / i, (long long)n); j++) {
				sum++;
			}
		}

		if (sum >= k) {
			result = start;
			right = start - 1;
		}
		else {
			left = start + 1;
		}
		start = (left + right) / 2;
	}
	cout << result;
	return 0;
}
Written on May 13, 2021