백준 1300 K번째 수

이진 탐색 문제 중, 조금 특이해 보여서 풀어보았다.

처음에 그냥 행렬만들고 정렬해서 하면 되겠지 하다가 골드 3인거 보고 아 안되겠구나 했다.

이거 문제를 어떻게 접근해야하나 고민하다가 답이 안나와서 좀 찾아봤는데, 조금 머리를 써야되는 풀이였다.

 

만약 이 배열 B에서 11번째, 즉 B[11]을 찾고 싶다고 가정하자.

B[11]의 숫자가 x라고 하면, 전체 숫자 중에서 x보다 작거나 같은 숫자의 수가 11보다 작으면 안된다.

만약 작다면, x가 더 커져야 한다.

이 (전체 숫자에서 x보다 작거나 같은 숫자의 수)를 가지고 이진 탐색을 한다.

 

그렇다면 이 (전체 숫자에서 x보다 작거나 같은 숫자의 수) 는 어떻게 구하느냐 하면, 각 행별로 계산을 접근해본다.

각 행은 i*1, i*2, i*3.... 의 모양이고, x를 i로 나눈 몫과 n 중 작은 것이 그 행에서 m 보다 작거나 같은 개수이다.

이 연산을 각 행마다 연산 후 더하면 전체 숫자 중 x보다 작거나 같은 숫자의 개수 이다.

 

이 값을 가지고 이진 탐색을 하면 된다.

---

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    int n, k;
    std::cin >> n >> k;
    
    int start = 1;
    int end = k; // b[k] 는 k보다 작거나 같음. => 이분 탐색의 종료점 = k;
    int mid, ret = 0;

    
    // b[11] 을 찾고 싶을때 -> b[11]의 숫자가 x라고 하면, 전체 숫자 중에서 x보다 작거나 같은 숫자의 수가 11보다 작으면 안됨.
    // 만약 그렇다면, 찾는 숫자의 범위를 큰 쪽으로 옮겨야.

    // 각 행에서 특정 숫자 m보다 작거나 같은 개수를 찾기
    // 행 번호 i이면, min(m / i, N)

    while (start <= end)
    {
        mid = (start + end) / 2;

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

        if (count >= k)
        {
            ret = mid;
            end = mid - 1;
        }
        else
            start = mid + 1;
    }
    std::cout << ret;
}

 

코드를 더 뜯어보고 고민을 좀 해봐야겠다. 코드가 아주 간소하긴 한데 좀 이 배열에서 숫자를 세는 매커니즘과 이진 탐색으로 어떻게 값을 도출해 내는지에 대해 더 이해가 필요한 것 같다.

 

오늘도 평온한 하루가 되길. 슨민.