풀이
임의의 숫자 m을 골라서 K번째 숫자인지 판단해보자!
그 임의의 숫자 m은 무려 O(log K)에! 무려 이분 탐색으로 찾아보자!
그렇다면 떠오르는 질문, m 보다 작은 숫자의 개수를 어떻게 하면 빠르게 구할 수 있을까?
A[i][j]에서, i행에 속한 숫자들은 i*j이므로 모두 i의 배수이다.
그러므로 min(mid/i, N)이 i번째 행에서 mid보다 작은(= 임의의 m보다 작은) 숫자들의 개수가 된다.
eg. N = 1000인 경우, 첫 mid가 1000*1000/2 = 50만이 되는데, 50만/i가 N을 넘어갈 수 있으므로 min(mid/i, N)을 해준다.
조금 더 쉽게 쓰자면, i행의 숫자들은 i*1, i*2, i*3, ..., i*N으로 구성되어 있다.
i행의 숫자들 중 m보다 작거나 같은 숫자는 (i*j <= m)를 만족하는 j의 개수이고
이는 i*1, i*2, ..., i*j이므로, m/i와 같은 값이 된다.
각 O(log K)에 대해, 1부터 N까지 모든 i행에 대해 m/i를 수행해주어야 하므로
총 시간 복잡도는 O(NlogK)가 된다.
코드
#include <stdio.h>
#include <algorithm>
int main() {
int N, K;
scanf("%d %d", &N, &K);
int left = 1, right = K, ans;
while (left <= right) {
long long cnt = 0;
int mid = (left + right) / 2;
for (int i = 1; i <= N; i++) cnt += std::min(mid / i, N);
if (cnt < K) left = mid + 1;
else ans = mid, right = mid - 1;
}
printf("%d", ans);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이