[백준][C++] 1300: K번째 수 (bisearch)

문제

1300: K번째 수

풀이

• K번째 수를 구하기 위해 배열에 숫자를 저장하고 정렬하려 했지만, 입력의 크기가 크기 때문에 다른 방법으로 문제를 해결해야한다.

• 문제에서 주어진 이차원 배열은 특정한 규칙이 있으므로, 이를 활용하여 따로 저장하지 않고 문제를 풀 수 있어 보인다.

• 이차원 배열에서 하나의 값이 몇번째 위치에 있는지 알려면, 그 값보다 작은 것의 개수와 큰 것의 개수를 세면된다.

  • 그러면 그 값이 속한 범위를 구할 수 있다.

• 이차원 배열이 생성되는 규칙에 의해여 i열에 속한 값들 중에서 우리는 어떠한 값보다 작은 값들의 개수를 알 수 있다.

  • 어떠한 값을 i로 나누면, i와 곱해서 생성되는 어떠한 값보다 작은 수의 개수를 구할 수 잇다.

• 이제 우리는 1~N까지 순회하면, O(N) 시간에 하나의 값의 위치를 파악할 수 있다.

• 여기서 이진 탐색을 사용하면, O(NlogN) 시간에 모든 값의 범위에서 특정한 위치에 있는 값을 찾을 수 있다.

이진 탐색

• 값의 범위는 1~N*N 이므로 하한, 상한을 이로 설정할 수 있다.

  • 하지만 잘 생각해보면 K + 1 보다 항상 작은 값이 나온다.

• 이제 중간값 mid를 구하여 이 값의 최소 위치가 K 와 같거나 작은지 확인한다.

  • 만약 작거나 같으면 더 큰 값이 올 수있기 때문에, 하한인 lo에 mid를 대입한다.

    ll lo = 1;
    ll hi = K+ 1L;
    while (lo + 1L != hi)
    {
        ll mid = (lo + hi) / 2;
        if (isOkay(mid, N, K))
        {
            lo = mid;
        }
        else
        {
            hi = mid;
        }
    }

작은 값들의 개수 구하기

• 한 열 i 에서 작은값들의 개수는 mid/i로 구할 수 있다.
• 여기서 mid 가 i의 배수가 된다면 그 값은 카운트에서 제외해야한다.(작은 값들만 카운트)
• 그리고 배열의 크기는 NxN이므로, N보다 클 수 없다.

bool isOkay(ll mid, ll N, ll K)
{
    ll count = 1L;
    for (ll i = 1; i <= N; i++)
    {
        ll smallCount = mid / i;

         if (mid%i == 0 && N >= smallCount)
         {
             smallCount--;
         }
         count += min(N, smallCount);
    }
    return count <= K;
}

주의할점

• 카운트 시작은 1이다.
  • 어떠한 값의 위치이므로, 작은것들의 개수 + 1 이 해당 값의 최소 위치가 된다.

코드

using ll = long long;

bool isOkay(ll mid, ll N, ll K)
{
    ll count = 1L;
    for (ll i = 1; i <= N; i++)
    {
        ll smallCount = mid / i;

         if (mid%i == 0 && N >= smallCount)
         {
             smallCount--;
         }
         count += min(N, smallCount);
    }
    return count <= K;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll N;
    ll K;
    cin >> N >> K;

    ll lo = 1;
    ll hi = K+ 1L;
    while (lo + 1L != hi)
    {
        ll mid = (lo + hi) / 2;
        if (isOkay(mid, N, K))
        {
            lo = mid;
        }
        else
        {
            hi = mid;
        }
    }
    cout << lo;
}