k번째 수

1 2 3
2 4 6 
3 6 9

1 2 2 3 3 4 6 6

 

N이 3일 때는 이렇게 B 배열이 작성된다.

B의 k번째 수를 구해야 한다.

즉, A에 있는 N제곱개의 숫자 중에서 k번째로 작은 수를 구하는 문제이다.

그냥 N제곱 크기의 배열을 만들어서 정렬을 해버리면 N^2 * 2logN의 시간이 걸려서 애매하다.

시간이 되더라도 어차피 N^2 크기의 배열을 만들 메모리가 없기 때문에 안된다.

 

다른 방법을 찾아야 한다.

어떤 숫자를 정하고 그 숫자가 몇번째로 작은 수인지 구하는 과정은 N의 시간만에 할 수 있다.

그럼 그 숫자가 x번째로 작은 수라고 가정하고 x가 k보다 작으면 숫자를 키우고, k보다 크면 숫자를 줄이면 된다.

즉, 이분탐색으로 해결할 수 있다.

long long bin_search(long long s, long long e)
{
    if(s==e) return s;
    long long m = (s+e)/2;
    long long cnt = 0;
    for(int i=1;i<=N;i++)
    {
        cnt += min(N,m/i);
    }
    if(cnt<k)
    {
        return bin_search(m+1,e);
    }
    else
    {
        return bin_search(s,m);
    }
}

숫자를 m으로 정하고 m 보다 작거나 같은 수의 개수를 cnt에 담았다.

for문 안에서 A배열을 한줄씩 돌면서 최대 N개, m/i로 개수를 구해서 더해줬다.

그리고 cnt와 k를 비교해 범위를 이분탐색으로 좁혀가며 k번째 수를 구했다.

#include<stdio.h>
#include<algorithm>
using namespace std;
long long N,k;
long long bin_search(long long s, long long e)
{
    if(s==e) return s;
    long long m = (s+e)/2;
    long long cnt = 0;
    for(int i=1;i<=N;i++)
    {
        cnt += min(N,m/i);
    }
    if(cnt<k)
    {
        return bin_search(m+1,e);
    }
    else
    {
        return bin_search(s,m);
    }
}
int main()
{
    scanf("%lld %lld",&N,&k);
    printf("%lld",bin_search(1,k));
}

전체 코드이다.