STUDY NOTE · 개념 정리
매개변수 탐색으로 푸는 K번째 수 (BOJ 1300)
Algorithm
N×N 배열의 A[i][j] = i×j 값을 일렬로 정렬했을 때 K번째 수를 구하는 문제. N이 최대 105라 배열을 만들 수 없다.
질문을 뒤집기
"K번째 수는 무엇인가?" 대신 "x 이하인 수는 몇 개인가?"를 묻는다. 이 개수는 x에 대해 단조 증가하므로, 개수가 처음으로 K 이상이 되는 가장 작은 x가 답이다. 이렇게 답 자체를 이분 탐색하는 방식을 매개변수 탐색이라고 한다.
x 이하인 수 세기
i행은 i, 2i, 3i, …, Ni 이므로 x 이하인 개수는 min(x / i, N)개다.
long long n, k;
cin >> n >> k;
long long lo = 1, hi = k, ans = k; // 답은 k를 넘지 않는다
while (lo <= hi) {
long long mid = (lo + hi) / 2, cnt = 0;
for (long long i = 1; i <= n; i++) cnt += min(mid / i, n);
if (cnt >= k) { ans = mid; hi = mid - 1; }
else lo = mid + 1;
}
cout << ans;
왜 답이 k를 넘지 않을까
1행에는 1, 2, …, N이 있고 다른 행에도 작은 수가 많아서, k 이하인 수는 항상 k개 이상 존재한다. 그래서 탐색 범위를 [1, k]로 잡을 수 있다.
시간 복잡도
이분 탐색 O(log K) × 개수 세기 O(N) = O(N log K). 공유기 설치(BOJ 2110), 랜선 자르기(BOJ 1654)도 같은 틀로 풀린다: "답이 x일 때 조건을 만족하는가?"가 단조로우면 답을 이분 탐색한다.