[백준 1300번] K번째 수

문제 링크: 1300번 K번째 수

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

 

이 문제를 읽은 뒤 parametric search라는 알고리즘 자체를 떠올리는 것 자체가 난해한 과정이며, 해당 알고리즘으로 풀 수 있는 문제라는 것을 인지하더라도 다소 헤매게 되어있습니다.

일단 naive한 풀이는 왜 안될까요? N은 10⁵보다 작거나 같은 자연수이므로 배열의 모든 숫자를 일일이 나열하여 정렬하고자 하면 10¹⁰개에 달하는 수를 다루어야 하기 때문입니다.

일일이 각 숫자의 개수를 모두 계산하자니 규칙을 찾기가 힘들 뿐더러, 결국 많은 양의 연산이 필요합니다.

우리는 이 문제를 "어떤 수 x가 i번째 숫자일 때, i는 k보다 크거나 같은가?"라는 결정 문제로 바꾸어 풀 수 있습니다. 간단한 예를 들어 N = 4일 떄를 살펴보겠습니다.

 

1   2   2   3   3   4   4   4   6   6   8   8   9   12   12   16

 

우리는 13번째 숫자가 무엇인지 알고 싶습니다. 이를 위해서 직접 13번째 숫자를 찾아나가는 것이 아니라, 위 예에서는 다음과 같은 과정으로 진행됩니다. 다만 여기서 전제를 하나 두는데, x가 i번째 숫자일 때, i는 같은 숫자 여러개 중 마지막 숫자의 인덱스를 나타냅니다.

 

1. [1, 16] 중에 정답이 있으므로 (1+16)/2 = 8을 살펴봅니다.

"어떤 수 x가 i번째 숫자일 때, i는 k보다 크거나 같은가?"

→ "어떤 수 8이 12번째 숫자일 때, 12는 13보다 크거나 같은가?"

아니오. 8은 12번째 숫자이므로, 13보다 작습니다.

그렇다면 8은 절대로 정답이 안되겠죠. 위에서 밑줄친 전제 때문에 13번째 숫자만 해도 무조건 8보다는 크기 때문입니다.

정답의 구간을 [8+1, 16]으로 좁힙니다.

1   2   2   3   3   4   4   4   6   6   8   8   9   12   12   16

 

2. [9, 16] 중에 정답이 있으므로 (9+16)/2 = 12를 살펴봅니다.

"어떤 수 x가 i번째 숫자일 때, i는 k보다 크거나 같은가?"

→ "어떤 수 12가 15번째 숫자일 때, 15는 13보다 크거나 같은가?"

예. 12는 15번째 숫자이므로, 13보다 큽니다.

그렇다면 12는 정답이 될 수 있을까요? 네, 가능합니다. 어떤 특수한 경우에는, 구하고자 하는 13번째 숫자를 포함해서, 13~15번째 숫자까지가 모두 12일 수도 있기 때문입니다.

이를 고려하여 정답의 구간을 [9, 12-1]이 아닌 [9, 12]로 좁힙니다.

1   2   2   3   3   4   4   4   6   6   8   8   9   12   12   16

 

3. [9, 12] 중에 정답이 있으므로 (9+12)/2 = 10을 살펴봅니다.

"어떤 수 x가 i번째 숫자일 때, i는 k보다 크거나 같은가?"

→ "어떤 수 10이 ?번째 숫자일 때, ?는 13보다 크거나 같은가?"

어라, 여기서 문제가 발생했습니다. 10이라는 숫자 자체가 존재하지 않기 때문입니다. 사실 여기서 알 수 있는 부분은, 어떤 수가 몇 번째 숫자인지를 어떻게 알 수 있을까요? 여기선 손으로 풀고 있으니까 직접 세어서 알 수 있었으나, 실제로는 무언가 다른 과정이 필요하겠죠. 어려운 건 아니고, 좀 무식하게 구할 수 있습니다.

 

	1	2	3	4
1	1	2	3	4
2	2	4	6	8
3	3	6	9	12
4	4	8	12	16

 

위의 표에서 9보다 같거나 큰 수를 구하기 위해서, 1부터 n까지 순환하면서 9로 나눈 몫을 더해주면 됩니다. 그래서 2일 때에는 2x1, 2x2, 2x3, 2x4해서 4=9/2개, 3일 때에는 3x1, 3x2, 3x3해서 3=9/3개, 4일 때에는 4x1, 4x2해서 2=9/4개입니다. 다만 여기서 1일 때는 문제가 되는데,  9=9/1이지만 N = 4이기 때문에 5, 6, 7, 8, 9는 존재하지 않죠.

그래서 14line과 같이 min(n, m / i)라는 코드가 작성되는 것입니다.

 

여하튼 이런 과정을 따르면, 10은 min(4, 10/1) + min(4, 10/2) + min(4, 10/3) + min(4, 10/4) = 4 + 4 + 3 + 2 = 13번째 수로 판정이 됩니다.

 

여기서 10이 정답으로 최종 판정되면 문제가 되는데요, N = 4일 때의 배열에 10은 존재하지 않기 때문입니다. 하지만 다행이도 그럴 일은 없습니다. 어떤 수가 정답이라면 반드시 그 수까지 위에서 좁혀서 내려오기 때문입니다. 실제로 계속해서 보면 이 말이 사실임을 알 수 있습니다.

 

"어떤 수 x가 i번째 숫자일 때, i는 k보다 크거나 같은가?"

→ "어떤 수 10이 13번째 숫자일 때, 13은 13보다 크거나 같은가?"

예. 10은 13번째 숫자입니다. 실제로는 아니지만요.

 

4. [9, 10] 중에 정답이 있으므로 (9+10)/2=9를 살펴봅니다.

"어떤 수 9가 i번째 숫자일 때, i는 k보다 크거나 같은가?"

→ "어떤 수 9가 13번째 숫자일 때, 13은 13보다 크거나 같은가?"

예. 9는 13번째 숫자입니다. 진짜로요.

1   2   2   3   3   4   4   4   6   6   8   8   9   12   12   16

 

이러한 과정을 통해 우리는 배열의 k번째 수를 알아낼 수 있습니다. 시간복잡도는 O(nlogn)이 되겠네요.

 

 

 

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll n, k;

ll min(ll a, ll b) {
    return a < b ? a : b;
}

ll f(ll m) {
        ll cnt = 0;
        for (int i = 1; i <= n; i++) {
            cnt += min(n, m / i);
        }
        return cnt;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k;
    ll l = 1, r = n * n, m = -1;
    while (l <= r) {
        m = (l + r) >> 1;
        ll t = f(m);
        if (l == r) break;
        if (t >= k) r = m; else l = m + 1;
    }
    cout << m;
    return 0;
}