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

이분탐색을 시작하는 분들도 쉽게 풀만한 문제라고 생각된 문제중 하나였다. 

배열 A[i][j] = i*j라는 특성을 사용해서 결국 행*열의 곱이라는 말이다. 굳이 일차원배열로 늘어놓고

정렬을 안해도되고, 하게된다면 시간초과의 난관을 겪을 것이다. 

예를들어보자 n이 5일때 1*1, 1*2, 1*3, 1*4, 1*5, 2*1, ... 이다.

6이라는 수를 가정하고 몇번째 수인지 따저본다. 1행에서 6보다 작은수는 6/1 즉 6개 

2행에서는  6/ 2 = 3개 이런식이다. 실제로 2,1   2,2    2,3 이렇게 3개인것이다. 

따라서 그냥 lft를 1로 설정하고 k번째 수가 절대 k보다 클리는 없으므로 k로 상한을 잡고 

이분탐색을 돌리면 되는것이다. 

실제로 풀어보면 이분탐색에 대한 자신감이 팍팍 솟는 문제!

1300번: K번째 수

1300번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 K번째 수 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 2495 772 567 35.130% 문제 세준이는 N*N크기의 배열을 만들었다. (배열의 방 번호는 1부터 시작한다.) 그 배열을 A라고 했을 때, 배열에 들어가는 수는 A[i][j] = i*j 이다. 세준이는 이 수를 일차원 배열 B에 넣으려고 한다. 그렇게 되면, B의 크기는 N*N이 될 것이다. 그러고 난 후에, B를 정렬해서 k번째 원소를 구하려고 한

www.acmicpc.net

https://www.acmicpc.net/problem/1300

<Code>

// pda_pro12
#include<algorithm>
#include<iostream>
#define N_ 100000
using namespace std; 
typedef long long ll; 
 
int a, b, ans; ll lft, rgt; 
 
int main() {
    cin >> a >> b;
 
    lft = 1;  rgt = b; 
 
    while (lft <= rgt) {
        int mid = (lft + rgt) >> 1;   // 가정된 K번째 
        ll Sum = 0; 
        for (int i = 1; i <= a; i++)    // 행마다 mid보다 작은수의 갯수를 측정
            Sum += min(a, mid / i); 
        if (Sum >= b)
            rgt = mid - 1, ans = mid;
        else
            lft = mid + 1; 
    }
    cout << ans; 
    return 0; 
}