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

1300번: K번째 수

이분 탐색

---

1. 문제해결 아이디어

일단 n이 최대 100000 이므로 B배열을 실제로 만들어 주는건 불가능하다.

i번째 행은 i의 배수의 집합임을 이용하자

N = 5, K = 17 이 주어졌을 때.

 

이 문제를 이분탐색으로 풀기 위해서 5x5의 절반인 12를 최초 mid로 설정하자(lo = 0, hi = 25)

12는 위 표에서 몇 번째일까?

• 1행은 모두 12보다 같거나 작다 -> cnt += 5
• 2행도 모두 12보다 같거나 작다 -> cnt += 5
• 3행은 4열까지만 12보다 같거나 작다 -> cnt += 4
• 4행은 3열까지만 12보다 같거나 작다 -> cnt += 3
• 5행은 2열까지만 12보다 같거나 작다 -> cnt += 2

cnt = 19가 되고 K=17보다 크기 때문에 mid값을 감소시켜야 함을 알 수 있다 -> hi = mid-1, mid = (lo + hi) / 2 = 5

mid는 (lo + hi) / 2 로 재설정해주고 위 작업을 반복하면 O(NlogK)만에 K번째 수를 구할 수 있다

---

2. 코드 설명

<+8> ~ <+18> lessNum_inMatrix(long long) : 행렬에서 mid이하인 수의 개수를 리턴하는 함수

<+27> ~ <+35> : 

mid와 같거나 작은 수의 개수가 K보다 작으면 K번째 수는 적어도 현재 mid보다는 크다는 말이므로 lo를 mid+1로 만들어서 탐색 범위를 절반 줄여준다

mid와 같거나 작은 수의 개수가 K와 같거나 크면 K번째 수는 현재 mid이거나 mid보다 작다는 말이므로 hi를 mid-1로 만들어준다

lo가 hi보다 커진다면 else 부분 조건이 반복되고, K번째 수가 현재 mid라는 뜻을 가지게 된다

#include <iostream>
 
using namespace std;
 
long long N, K;
 
// 행렬에서 mid와 같거나 작은수의 개수를 리턴
long long lessNum_inMatrix(long long mid){
    long long cnt = 0;
    for(int i = 1; i <= N; i++){
        // i행은 i의 배수의 집합이므로 
        // mid를 i로 나눠주면 mid가 i행에서 몇 번째에 위치하는지 알 수 있다
        // i행의 최댓값보다 mid/i가 더 크다면 N(행의 크기)을 cnt에 더해준다
        cnt += min(N, (long long)mid/i);
        if(i > mid) break;
    }
    return cnt;
}
 
void Matrix_BS(){
    long long lo = 1;
    long long hi = N*N;
    
    int res = 0;
    
 
    while(lo <= hi){
        long long mid = (lo + hi)/2;
        // mid와 같거나 작은 값의 개수가 K보다 작으면
        if(lessNum_inMatrix(mid) < K) lo = mid + 1;
        else{
            res = mid;
            hi = mid - 1;
        }
    }
    cout << res;
}
 
int main(){
    cin >> N >> K;
    Matrix_BS();
    
    return 0;
}