[boj] 백준 1300 k번째 수 (c++) - 이분 탐색

[문제]

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

1300번: K번째 수

 

[풀이]

문제 자체는 단순하지만 n의 크기가 너무 커 2차원 배열을 1차원 배열로 직접 옮겨서는 해결할 수가 없다.

따라서 이분 탐색을 이용해야 한다.

먼저 low는 1, high는 n*n으로 세팅한 후 mid 값보다 작거나 같은 수들의 개수를 구한다. 

예를 들어, n = 4, k = 7 이면 다음과 같은 2차원 배열이 될 것이다.

 

1	2	3	4
2	4	6	8
3	6	9	12
4	8	12	16

 

처음 mid 값은 8이고, 8보다 작거나 같은 수의 개수를 구해야 한다.

i = 1일 때, 1, 2, 3, 4 ... 와 같이 증가하므로 8보다 작거나 같은 수는 1~8 까지 8개, 즉 8/1 개이다.  그러나 n = 4이므로 4개가 된다.

i = 2일 때, 2, 4, 6, 8 ...와 같이 증가하므로 8보다 작거나 같은 수는 8/2 = 4개이다. 

i = 3일 때, 3, 6, 9, 12 ...와 같이 증가하므로 8보다 작거나 같은 수는 8/3 = 2개이다.

i = 4일 때, 4, 8, 12, 16 ...와 같이 증가하므로 12보다 작거나 같은 수는 8/4 = 2개이다.

총 4 + 4 + 2 + 2 = 12개가 된다.

즉, mid보다 작거나 같은 수는 min(mid/i, n) 개의 합이 된다.

 

이때, 우리가 구하고자 하는 k번째 수는 7번째 수이고, 이는 12보다 작은 수이다. 

따라서 mid 값을 앞으로 이동해야 하므로 high를 mid-1로 조정해준다.

만약 k가 count보다 크다면 mid값을 더 키워야하므로 low를 mid+1로 조정해주면 된다.

 

[코드]

 

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>

using namespace::std;

long long n, k;
long long low, high, mid;
long long cnt;

long long count(long long mid)
{
    long long count = 0;
    for (int i = 1; i <= n; i++)
    {
        count += min(mid / i, n);
    }
    return count;
}

int main()
{
    cin >> n >> k;

    k = min((long long)1000000000, k);

    low = 1;
    high = n * n;

    while (low <= high)
    {
        mid = (low + high) / 2;

        cnt = count(mid); // Mid보다 작거나 같은 수들의 개수

        if (cnt >= k)
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }
    cout << low;
}