1300 : K번째 수

풀이

임의의 숫자 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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-02-20 22:24

Read more posts by this author