[BOJ 1300] K번째 수

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

N*N크기의 배열에서 k번째 수를 구하는 문제이다. N의크기가 10^5까지이기 때문에 배열을 실제로 할당하는것은 메모리 초과 -> 터짐 

따라서 다른 방법을 생각해 보아야 한다. 

이 문제의 핵심은 parametric search를 이용하는 것이다. 

정답이 0과 N*N 사이의 한 정수이기 때문에 이분탐색방식을 이용하여 접근한다. 

핵심은 임의의 수를 답이라고 가정하고, 그 수가 k번쨰 수인지 확인하는 방식이다. 

여기서  k번째 수라는 뜻은 자기보다 작은 숫자가 k-1개라는 뜻임을 기억하자.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <stack>
#include <utility>
#include <set>
#include <tuple>
typedef long long ll;
 
#define INF 2e9
 
using namespace std;
 
ll n,k,l,r,ans;
 
int main(){
    scanf("%lld%lld" , &n,&k);
    l = 1;
    r = n*n;
    ans = 0;
    while (l <= r) {
        long long mid = (l+r)/2;
        long long cnt = 0;
        for (long long i=1; i<=n; i++) {    // 개수구하기
            ll t = (mid/i);                 //각 줄마다 mid보다 작은 수 개수
            cnt += min(n,t);
        }
        if (cnt >= k) {
            ans = mid;
            r = mid-1;
        } else {
            l = mid+1;
        }
    }
    printf("%lld\n" , ans);
    return 0;}

생각보다 간단하게 답이 나오게 된다. 

1	2	3	4	5
2	4	6	8	10
3	6	9	12	15
4	8	12	16	20
5	10	15	20	25

라는 표에서 8이라는 숫자의 번째는 14~15일것이다. 즉 8보다 작은 수가 그만큼이라는 뜻이다.

따라서 28~31번째 줄의 의미는 각 행을 확인하면서 자신보다 작은 숫자가 몇개인지를 새고 그 cnt값이 k보다 작은지 큰지를 비교하는 방법이다. (각 줄마다 5,4,2,2,1)