백준 1300 - K번째 수, C++, 이분탐색

1300번: K번째 수

#include <iostream>
#include <algorithm>
using namespace std;

int n, k;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;

    int left = 1, right = k, res = -1;

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

        int count = 0;
        for(int i = 1; i <= n; i++)
            count += min(mid/i, n);
        
        if(count < k){
            left = mid + 1;
        }
        else {
            right = mid - 1;
            res = mid;
        }
    }

    cout << res << '\n';
}

---

주의점 2개만 발견하면 이분탐색으로 풀리는 문제입니다.

 

- k 번째 수를 B[k]라고 했을 때 B[k] <= k 가 됩니다.

- 각 행에서 mid 보다 작은 수의 마지막을 i*j라 하면 j <= mid / i 가 됩니다.

 

위 두가지 방법만 잘 쓰면 되는 문제였는데 left += mid = 1이라는 괴상한 문법을 써서 계속 시간초과가 났던 문제였습니다. IDE에서는 왜 된거지..