[BOJ] 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