BOJ - K번째 수(1300)

골드4 : 이분 탐색 문제이다.

생각

어려웠다. 여러가지 배열이 섞이고, 계산하는 방법을 생각하지 못했다. 이 문제를 풀면서 배운 것은, 정말 컴퓨터처럼(센다..) 생각해야 된다는 것.. 그리고 예시를 놓고, 이것을 실제로 써보면서 이상적으로 풀 생각을 하지말고 try & modify 하는 것이다. 너무 뼈저리게 느꼈다..

그래서, 지금부터 써보겠다. 이 문제에서 고려해야 하는 점은 크게 2가지 이다.

센다.

이분 탐색으로 풀린다는 것은 알았으나, K번째 수가 N이라고 제안한 이후에, 어떻게 K번째 수인지를 도출할 것인지에 대한 고민이 많았다. 즉, 제안한 숫자에 대해 이 숫자가 몇번째 수인지를 output으로 내놓을 함수를 짜야한다. 처음에 이것은, 제안한 숫자에 대한 제곱수를 찾아 필요없는 수를 제끼고..이런 방법으로 하려고 했는데, 컴퓨터는 정말 단순하게 생각하는 것이 핵심인 것 같다.

   1   2   3   4   5   6   7   8   9  10
   2   4   6   8  10  12  14  16  18  20
   3   6   9  12  15  18  21  24  27  30
   4   8  12  16  20  24  28  32  36  40
   5  10  15  20  25  30  35  40  45  50
   6  12  18  24  30  36  42  48  54  60
   7  14  21  28  35  42  49  56  63  70
   8  16  24  32  40  48  56  64  72  80
   9  18  27  36  45  54  63  72  81  90
  10  20  30  40  50  60  70  80  90 100

내가 만약, 25라는 숫자를 제안했다고 하자. 그렇다면, 1번째 행에서 부터, 이 숫자보다 작은 것이 몇개있는 지를 센다. 그렇다면 10이다. 3번째 열에서는 8이다. 이 숫자들은, i번째 행의 숫자로 제시한 숫자를 나눈 몫으로 가능하다. 이 문제가 쉬운 이유이다. 그렇기 때문에 내가 제안한 숫자의 번째 수를 계산하는 것은 $O(N)$에 가능하다.

ll f(ll num){
    ll count = 0, numbering, current = 0;
    for (int i = 1; i <= N; i++) {
        if (num/i > N) {
            numbering = N;
            current = i * N;
        } else {
            numbering = num/i;
            current = num/i * i;
        }
        count += numbering;
    }
    return count;
}

이 과정을 N이 3일 때 정리해보면 다음과 같다.

 1 2 3
 2 4 6
 3 6 9

 제시하는 숫자 : 1 2 3 4 5 6 7 8 9
 count      : 1 3 5 6 6 8 8 8 9

어떤 것이 답인가?

 1 2 3
 2 4 6
 3 6 9

 제시하는 숫자 : 1 2 3 4 5 6 7 8 9
 count 함수  : 1 3 5 6 6 8 8 8 9

 B[]        : 1 2 2 3 3 4 6 6 9
 번째 수      : 1 2 3 4 5 6 7 8 9

하지만 이렇게 되면 조금 문제가 발생한다. 원하는 K가 8, 즉 8번째 수라면 7을 제안해도 8, 6을 제안해도 8, 8을 제안해도 8이다. 그런데, 7을 제안하면 A배열에 없기 때문에 답이 아니다. 또한, K가 7일 경우, count함수를 통과시켜 나온 리턴 값에는 7이 없다. 하지만 7번째 수는 분명히 존재한다.

이 문제는 숫자가 연속적으로 나열된 문제가 아니기 때문에, 특정 숫자에 대한 번째만이 존재한다. 다시 말하면 6이라는 숫자는 실제 B배열에서 7번째, 8번째 숫자이지만, 7이라는 숫자는 A배열에 없기 때문에 N번째 숫자라는 개념 자체가 불가능 하다. 즉, 7이라는 숫자를 제안했을 때, A배열에서 있다고 가정하고 숫자를 세면, 6을 세었을 때와 같은 count가 나오나, 7이라는 숫자가 없기 때문에 답이 아니다.

숫자의 범위 때문에, 답을 제시하는 방법을 사용하긴 해야한다. 그렇다면 어떻게 A배열에 있으면서, 원하는 K번째가 있는 수를 제시할 수 있을까?

K보다 count가 큰 녀석은 답의 후보이다.

이것을 알기 위해서, 일단 이분 탐색이 맞다하고 생각을 해보자.

1 2 3
2 4 6
3 6 9

K = 7

제시하는 숫자 : 1 2 3 4 5 6 7 8 9
count 함수  : 1 3 5 6 6 8 8 8 9

B[]        : 1 2 2 3 3 4 6 6 9
번째 수      : 1 2 3 4 5 6 7 8 9

start : 1  end : 9  제시 : 5
start : 6  end : 9  제시 : 7
start : 6  end : 6  제시 : 6

K = 7인 상황에서 생각해보자. 먼저 (1+9)/2 = 5를 제안한다. 이 때의 함수 통과 값은 6이므로, K보다 작다. 따라서 값을 올려 제안한다.

이번엔 (6+9)/2 = 7을 제안한다. 이 경우 함수 통과 값은 8이다. K보다 작다. 따라서 제시하는 값을 낮춘다.

마지막으로 (6+6)/2 = 6를 탐색한다. 이 경우 count는 8이다. 그리고 나서 L, R가 역전되므로 끝난다. 하지만 답은 찾았다. 6이다.

즉, count가 굳이 K와 같지 않더라도 답을 구할 수 있다.

이 부분을 잘 생각해보자.
7을 세었을 때와 6을 세었을 때, 같은 번째 수(8)라는 결론이 나오나, 우리는 8이라는 숫자가 처음 등장하는 숫자를 답으로 제안해야 한다. 7을 제안했을 때, 8이 나오는 이유는, 7이라는 숫자가 A배열에 없기 때문이다. 실제로 있는 수는, count함수를 돌렸을 때, 처음으로 8이라는 숫자가 나오는 경우, 해당 숫자를 A배열에 있는 수라고 생각할 수 있다. (잘 생각해보자.) 그렇기 때문에, 우리는 이분 탐색의 분기를 다음과 같이 정해야 한다.

1. count가 K보다 작다.
   • 이 구간에는 답이 존재할 수 없으므로 더 큰 값을 탐색한다.
2. count가 K보다 크다.
   • 이 구간에는 답이 존재할 수 있다. 그렇기 때문에 이 때 제시한 값은 답의 후보로 채택한다.
   • 그리고, count가 K와 같은 구간을 찾기 위해 더 작은 값을 탐색한다.

이 과정을 거치게 되면서 우리가 하는 과정은, 최대한 K와 같은 값을 찾는다 이다. 이러한 방법은 곧, 같은 count값이 나오더라도, 그 같은 count값이 처음으로 등장하는 수를 답으로 채택한다. 라는 의미와 일치한다.

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<queue>
#include<functional>
 
using namespace std;
typedef long long ll;
ll MAX_NUM = 10000000000;
ll N, K;
 
ll f(ll num){
    ll count = 0, numbering, current = 0;
    for (int i = 1; i <= N; i++) {
        if (num/i > N) {
            numbering = N;
            current = i * N;
        } else {
            numbering = num/i;
            current = num/i * i;
        }
        count += numbering;
    }
    return count;
}
 
int main(){
    cin >> N >> K;
 
    ll ans = 0;
    ll start = 1, end = min(MAX_NUM, N*N);
 
    while (start <= end) {
        ll mid = (start+end)/2;
        ll count = f(mid);
        if (count < K) {
            start = mid+1;
        } else {
            ans = mid;
            end = mid-1;
        }
    }
    cout << ans << '\n';
}

Reference

• 백준(1300번) - K번째 수