[1300] K번째 수 (C++)

#include <iostream>

using namespace std;

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

    long N, k; cin >> N >> k;

    long low = 1;
    long high = k;
    long ans = 0;

    while (low <= high) {
        long mid = (low + high) / 2;
        long cnt = 0;

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

        if (cnt < k) low = mid + 1;
        else {
            ans = mid;
            high = mid - 1;
        }

    }

    cout << ans;
    
    return 0;
}

 

1. N의 크기가 10^5보다 작거나 같은 자연수이므로 NxN 배열을 생성하면 무조건 시간 초과

2. 3x3 배열을 생각해보면 1열은 1의 배수, 2열은 2의 배수, 3열은 3의 배수가 나열되어 있다

1	2	3
2	4	6
3	6	9

 

3. k의 최댓값은 N*N이며 k = N*N일 때  k - 1 >= N*N이므로, k번째 수는 k를 넘지 않는다

4. 3번에 기초하여, i = 1부터 i <= k일때 각 열에 i보다 작은 수가 몇 개 존재하는지 카운팅한다(cnt)

=> low = 1, high = k로 설정하고 이진 탐색을 사용하기 위해 mid = (low + high) / 2

5. 위 과정에서 cnt의 값이 k보다 작으면 low를 재설정하고, cnt의 값이 k보다 크면 high를 재설정하며 ans에 임시저장한다

6. low가 high보다 크면 while문을 종료하고 ans를 출력

 

 

 

 

---

2차원 배열에서 k번째 수를 구하기 위한 알고리즘을 생각해 내는 과정이 쉽지 않았다.

A[i][j] = i * j라는 구구단과 같이 이루어진 배열의 형태를 이용하여 규칙성을 찾아냈고, 이 규칙성을 이용해 각 열에 임의의 수 보다 작은 수가 몇 개 존재하는지 찾아내는 알고리즘을 생각해냈다.

구현은 쉬운 편이었다.