[백준] 1300 K번째 수

1300번: K번째 수

 

www.acmicpc.net

풀이

문제에 써있는 그대로 구현해서는 풀 수 없다. 이분탐색을 이용해서 해결하였는다. 이분탐색을 하는 아이디어는 다음과 같다.
임의의 숫자를 정해서 그 수보다 작은 수들의 개수를 세었을 때, 총 개수가 K인 경우를 확인한다. 이 아이디어를 사용할 수 있는 이유는 정렬된 일차원 배열에서 K번째 수라는 것은 결국 K번째로 작은 수라는 말이기 때문이다.

그렇다면 이제 K보다 작은 수를 세는 방법을 알아보자. 이 문제는 N이 최대 100000 이므로 100000 x 100000 크기의 배열을 생성해서는 해결할 수 없다.

예를 들어 N이 3인 상황에 5보다 작은 수를 찾고 싶은 상황이라고 하자.
1x1 1x2 1x3
2x1 2x2 2x3
3x1 3x2 3x3
의 형태로 A배열이 구성될 것이다. i x j < 5 인 수를 찾는 조건을 조금 수정하면 j < 5 / j 라고 할 수 있다. 결국 mid의 값을 설정하면 i번째 행에서 mid보다 작은 숫자의 개수는 mid / i 라고 할 수 있다. 따라서 이 조건으로 mid보다 작은 수들의 개수를 세서 left와 right를 조절하여 이분탐색하면 해결할 수 있다.

코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, k, ans;
    cin >> n >> k;
    int left = 1, right = k;

    while (left <= right) {
        long long cnt = 0;
        int mid = (left + right) / 2;
        // 한 행에서 mid보다 작은 수는 최대 n이므로
        for (int i = 1; i <= n; i++) cnt += mid / i < n ? mid / i : n;
        if (cnt < k) left = mid + 1;
        else {
            ans = mid;
            right = mid - 1;
        }
    }
    cout << ans << '\n';
    return 0;
}