#1300 K번째 수 (이분탐색)

 

k번째 수를 찾는 문제는 알고리즘 강의 시간에 시험문제로 나온 적이 있습니다.  퀵정렬 알고리즘을 가지고 k번째 원소를 찾는 문제였습니다.  사실 C++에 k번째 수를 찾는 함수를 제공하고 있으니, 이를 이용하면 아주 쉽게 찾을 수 있습니다.  가장 쉽게 풀 수 있는 방법은 정렬한 후에 k번째 원소를 출력하면 되겠지만, 이것은 너무 뻔한 이야기겠죠.

문제에서도 정렬한 다음에 K번째 수를 찾는다고 이야기가 나와있습니다.  이렇게 뻔한 방법으로 문제를 풀라는 것은 당연히 아닙니다.  숫자의 범위가 꽤 큽니다.  \(10^{10}\) 이니까, 그러면 int 자료형을 예상했을 때, 자료저장공간만 해도 \( 4 \times 10^{10} \) 이니까, 128MB 메모리 제한에 당연히 걸립니다.  자료공간에 필요한 40GB 입니다.  아마 자료공간 만드는 비용만 해도 수분 이상이 걸리겠죠.

 

Kth Number

 

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

1300번: K번째 수

결국 이 문제는 K번째 수를 찾는 일반 알고리즘은 아닙니다.  패턴을 찾고, 그것을 이용해야 합니다.  난이도가 Gold IV로 설정되어 있지만, 그것보다는 훨씬 쉬운 문제로 판단됩니다.

 

저는 이분탐색을 이용했습니다.  모든 배열 (i, j)의 값이 i*j의 값이기 때문에, m의 값이 주어졌을 때, m보다 작거나 같은 값이 있는 갯수는 모든 행에 대해서 m/i 가 됩니다.  이를 이용하면, \(O( N log N ) \)이 됩니다.  만약 정렬을 할 수 있다면, \( N^2 Log N \) 이 되었을 테고요, K번째 원소찾기를 이용했다면, \( O( N^2 ) \)이 되었을겁니다.  특정 패턴인 관계로 일반 알고리즘보다는 더 쉽게 찾을 수 있습니다.

 

이분탐색을 저는 low 는 k보다 작은 수입니다.  high는 k보다 크거나 같은 수입니다.  low와 high의 중간값을 가지고 k보다 작은 수가 나오면 low를 중간값으로 하고 크거나 같으면 high로 중간값으로 설정합니다.  실제 작은값의 갯수를 세는 것은 모든 행에 대해서 \( \lfloor m/i \rfloor \)의 값을 저장하면 됩니다.

\[ C_m = \sum_{k=1}^{n} \lfloor m/k  \rfloor \]

 

1	2	3
2	4	6
3	6	9

 

여기서 5번째 수를 찾으라고 한다면, 1, 2, 2, 3, 3, 4, 6, 6, 9이니까요, 3이 나와야겠죠.

L = 0, H = 9 로 시작을 합니다.

M = 4, C = 6  --> H = 4

M = 2, C = 3  --> L = 2

M = 3, C = 5  --> H = 3

으로 해서 3이라는 답을 찾았습니다.  이 문제에서 이분탐색에서 이하수를 찾아서 카운팅했을 때, K와 같은 수를 찾으면 틀립니다.  같은 수가 상당히 많이 생기기때문입니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//--------------------------------------------------------------------
//  baekjoon #1300 - Kth Number
//    - by Aubrey Choi
//    - created at 2019-07-14
//--------------------------------------------------------------------
#include <stdio.h>

int main()
{
  long long n, k, s, e, m, t, i;
  scanf("%lld%lld", &n, &k);
  for(s=0, e=n*n;s+1<e;)
  {
    m=(s+e)/2;
    for(i=1,t=0;i<=n;i++) t+=(m/i>n)?n:m/i;
    if(t<k) s=m; else e=m;
  }
  printf("%lld\n", e);
}