[Algorithm] Baekjoon 1300번 : K번째 수

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

1300번: K번째 수

long long n = 0;
long long m = 0;
 
 
void solution()
{
    long long left = 0;
    long long right = n * n + 1;
 
    while (left + 1 < right)
    {
        long long mid = (left + right) / 2;
        long long count = 0;
 
        for (long long i = 1; i <= n; ++i) // 행 순회.
        {
            count += min(n, mid / i);
        }
 
        if (count < m)
        {
            left = mid;
        }
        else
        {
            right = mid;
        }
    }
 
    cout << left + 1;
}
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
 
    cin >> n >> m;
    
    solution();
}

 

K번째 수를 찾는 문제다.

N값이 크기 때문에 컨테이너에 넣어서 정렬시키는 방식으론 풀지 못한다.

치사하게도 이분탐색인거는 알고 풀기 시작하긴 했는데... 도저히 재해석하지를 못했다.

키값이 뭔지 고민하다가 결국 다른 풀이를 참고했다.

 

일단 범위내의 숫자 (1~N*N)의 숫자들에 대해 각각 해당 숫자들보다 작거나 같은 갯수를 구하는게 중요하다.

단, 각각의 숫자에 대해서 N*N번 전부 체크하면 시간효율이 좋지않다.

다행히 각 행에 대해서 한번의 계산을 통해, 해당 행에 특정값 이하의 숫자가 몇개인지 바로 알 수 있다.

 

i번째 행의 k값 이하의 갯수 = min(N,k/i) 

 

i번째 행의 값들은 i의 배수라는 점을 이용한 식이다. (N은 N개를 넘는 수가 되는걸 막기위한 장치)

저게 맞는 식인지 긴가민가하다면 직접 N*N 행렬을 그리고 값을 대입해보면 감이 온다.

 

이후 구한 갯수가 m값의 '미만' 이라면, 기준으로 삼은 수가 좀 작다는거니까 범위를 우측으로 옮긴다.

구한 갯수가 m값의 '이상' 이라면, 범위를 좌측으로 옮긴다.

 

이렇게 이분탐색을 진행하면 된다.