[백준] 1300번 K번째 수

alirz-pixel·2022년 5월 15일
0

baekjoon

목록 보기
2/2

문제 바로가기

난이도 골드2
시간제한 2초
메모리 제한 128MB

📚 해설 및 코드

✏️ 문제 접근

문제에서의 B[k] = xB배열의 k번째 인덱스가 x라는 의미이다. 이를 반대로 해석하면 x 보다 작거나 같은 element의 개수는 k개라는 의미로도 해석이 가능하다. (B배열은 오름차순으로 정렬되어 있기 때문이다)

그러면 우리는 x의 값을 조정하면서(이분탐색) 문제에서 원하는 정답을 찾으면 된다.

✏️ x를 이용해 k값 찾기

int k = 0;
for (int i = 1; i <= n; i++) {
    k += min(n, x / i);
}

✏️ x의 후보

left : 1     right : n x n

✏️ 매개 변수 탐색 활용

위에서 구한 k값이 K(입력값) 보다 크다면, x(mid) 보다 작거나 같은 element의 개수가 K(입력값)보다 많다는 의미이므로 왼쪽 영역(x(mid)값이 줄어드는) 영역을 탐색하면 된다.. 그 반대의 경우엔 오른쪽 영역을 탐색하도록 한다.

추가적으로 왼쪽 영역을 탐색할 때의 mid 값은 ans의 후보가 될 수 있으므로 ans = mid를 해줘야 한다.

📑 코드

#include <algorithm>
#include <iostream>

using namespace std;

int main() {
	long long n;
	cin >> n;

	long long k;
	cin >> k;

	long long ans = 1;
	long long left = 1;
	long long right = n * n;
	while (left <= right) {
		long long middle = (left + right) / 2;

		long long cnt = 0;
		for (long long i = 1; i <= n; i++) {
			cnt += min(n, middle / i);
		}

		if (k <= cnt) {
			right = middle - 1;
			ans = middle;
		}
		else {
			left = middle + 1;
		}
	}

	cout << ans;
	return 0;
}

0개의 댓글