[백준] 1300번 - K번째 수 [Java][C++]

문제 링크

---

1. 문제 풀이

$N \times N$ 크기의 배열 $A$ 의 각 원소들은 $A[i][j] = i \times j$ 일 때, 이를 일차원 배열에 오름차순으로 옮겼을 때 $K$ 번째 수를 구해야 하는 문제다. $N$ 이 최대 $10^5$ 이어서 직접 배열을 만들고 정렬하는 방법으로는 해결할 수 없는데 이분 탐색과 매개 변수 탐색을 활용하면 해결할 수 있다.

포인트는 일차원 배열 $B$ 를 오름차순으로 정렬했을 때 $B[k]$ 의 값이 의미하는 것이 $B[k]$ 보다 작거나 같은 원소가 $B$ 에 $k$ 개 이상 있다는 점이다.

예를 들면 $N = 4$ 일 경우 $B[14] = 12$ 인데, 이는 $12$ 보다 작거나 같은 원소가 $14$ 개 이상 있다는 것이다.(인덱스는 1부터 시작)

그렇다면 임의의 수 $x$ 에 대해 $x$ 보다 작거나 같은 수가 $k$ 이상이 되는 $x$ 의 최솟값을 찾는 문제로 바꿔서 생각해볼 수 있다. 이때 정확한 $k$ 가 아닌 $k$ 이상인 이유는 중복된 수가 있기 때문으로 위 예시에서 $1$ 보다 작거나 같은 수는 $1$ 개, $2$ 보다 작거나 같은 수는 $3$ 개로 $x$ 보다 같거나 작은 수가 정확히 $2$ 개인 $x$ 는 존재하지 않는다. 따라서 $k$ 이상인 최솟값으로 $x$ 를 찾으면 된다.

임의의 수 $x$ 에 대해 $x$ 보다 작거나 같은 수가 $k$ 이상이 되는 $x$ 의 최솟값은 Lower Bound 이분 탐색을 활용하면 찾을 수 있는데 $k$ 의 범위가 $1$ ~ $\min(10^9, N^2)$ 이므로 이 중간 값 $mid$ 를 잡고 $mid$ 보다 작거나 같은 수의 개수를 세서 $k$ 보다 작으면 왼쪽 구간의 범위를 옮기고 $k$ 보다 크거나 같으면 오른쪽 구간의 범위를 옮기는 과정을 반복하면 된다.

그러면 이제 $mid$ 보다 작거나 같은 수의 개수만 셀 수 있으면 되는데 이는 $1$ 부터 $N$ 까지 $mid$ 를 각 수로 나눈 몫으로 구할 수 있다. $A$ 에서 $9$ 보다 작은 수의 개수는 1행에 $4$ 개, 2행에 $4$ 개, 3행에 $3$ 개, 4행에 $2$ 개가 있는데 이는 $9 / 1$, $9 / 2$, $9 / 3$, $9 / 4$ 와 같이 각각의 몫으로 구할 수 있다. 이 때 결과를 보면 알 수 있듯이 각 행에서 $mid$ 보다 작거나 같은 수로 포함되는 수의 개수는 이 몫과 해당 행 원소의 수인 $N$ 중 더 작은 값이다. 이제 이를 행 별로 전부 더한 값인 $cnt$ 를 $k$ 와 비교만 해주면 된다.

---

2. 코드

1. 이분 탐색 + 매개 변수 탐색 [Java]

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());

        System.out.println(lowerBound(N, k));
    }

    static int lowerBound(int N, int k) {
        int left = 1;
        int right = (int) Math.min(1_000_000_000, (long) N * N);

        while (left < right) {
            int mid = (left + right) / 2;

            long cnt = 0;
            for (int i = 1; i <= N; i++) {
                cnt += Math.min(mid / i, N);
            }

            if (cnt < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }
}

2. 이분 탐색 + 매개 변수 탐색 [C++]

#include <bits/stdc++.h>
using namespace std;

long long lower_bound_param(long long n, int k) {
    long long left = 1;
    long long right = min(1000000000LL, n * n);

    while (left < right) {
        long long mid = (left + right) / 2;

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

        if (cnt < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return right;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    cout << lower_bound_param(n, k);
}

---

3. 풀이 정보

1. 이분 탐색 + 매개 변수 탐색 [Java]

언어	시간	메모리	코드 길이
Java 11	120 ms	14276 KB	835 B

2. 이분 탐색 + 매개 변수 탐색 [C++]

언어	시간	메모리	코드 길이
C++ 17	28 ms	2020 KB	627 B

---