K번째 수 1300

문제

접근 방법

배열 A와 B의 크기는 10^10이 되기에 단순히 배열을 구성하는 것만으로도 시간 초과가 날 것이다.
다른 방법을 활용하여야 한다.

특정수 x가 k번째에 존재한다는 건 x보다 작은 값이 k개 존재한다는 것이다.

이차원 배열의 각 줄은 1부터 N까지의 곱이다.
1번째 줄은 1부터 N까지의 1을 곱한 것이고
i번째 줄은 1부터 N까지의 i를 곱한 것이다.
x를 각 줄의 값으로 나누어서 더하면 나보다 작은 값이 몇 개인지 알 수 있는 것이다.

3x3 크기의 6을 예시로 생각해 보자.
1번째 줄은 6을 1로 나누어 6이 나오지만, 최대 3개가 존재하기에 3이다. (1, 2, 3)
2번째 줄은 6을 2로 나누어 3이 나온다. (2, 4, 6)
3번째 줄은 6을 3으로 나누어 2가 나온다. (4, 6)
6의 k번째는 8이 나온다.
k가 7인 경우도 x는 6이다.

즉 찾고자 하는 k번째 값보다 같거나 큰 수를 찾으면 되는 것이다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll N, k, s, m, e, sum, ret;
int main()
{
    cin >> N >> k;
    s = 1;
    e = N * N;
    while (s <= e)
    {
        m = (s + e) >> 1;
        sum = 0;
        for (int i = 1; i <= N; ++i)
            sum += min((m / i), N);
        if (sum >= k)
        {
            ret = m;
            e = m - 1;
        }
        else
            s = m + 1;
    }
    cout << ret;
    return 0;
}

풀이

이분 탐색이라고 생각도 못 했다.
처음 봤을 때 마땅한 방법이 생각이 안 났다.
규칙이 존재할까 싶나 싶어서 1차원 벡터에 집어넣고 출력해 봤었는데 규칙을 찾기에는 복잡한 순서로 나열됐었다. 그래서 포기하고 다른 사람의 풀이를 봤다.

생각해 낼 수 있는 풀이었는가?라고 생각하면 반반인 것 같다. 2차원 배열에서 힌트를 얻는 건 가능했어도 이분 탐색으로 해결한다는 생각은 안 들었을 것 같다.

이분 탐색이란 점+특정 값보다 낮은 값의 개수를 구하는 방법을 생각해 내야 한다는 점에서 어려운 문제 같다.