백준 1300번 - K 번째 수

www.acmicpc.net/problem/1300

1300번: K번째 수

오랜만의 알고리즘 포스팅이다.

 

이번 주 우리 소학회의 공부 주제가 이분 탐색이라 이 문제를 풀어봤다. (KOALA 뽜이팅!!)

 

어제 그제 이분 탐색 기초 문제들을 몇 개 풀어본 뒤라 해볼 만할 거라고 생각해서 골드 문제에 도전했는데

 

문제를 보고 뭐지..? 란 생각이 들었다.

 

딱 봐도 일반적인 정렬은 무조건 아니고, 배열에 넣어서 계산하는 건 더더욱 아니고..

 

음...

 

음....??

 

음!!!!!!!!!!

 

갑자기 머릿속에 한 줄기 희미한 풀이법이 떠올랐다.

 

진짜 이렇게 표현하는 게 가장 적절한 것 같은데 정말 희미~한 가닥을 잡고 끈질기게 땅겨서 해결법을 찾았다.

 

이 맛에 알고리즘 하지ㅋㅋㅋㅋ (이럴 때 코드포스를 풀어야 되는데..)

 

어쨌든 내가 생각한 해결법은 다음과 같다.

 

B[k]를 이분 탐색으로 구할 것이다.

 

B[k]는 1~n제곱까지의 수가 가능하므로 해당 범위 안을 이분 탐색으로 돌며 답이 맞는지 아닌지를 체크해줄 것이다.

 

답이 맞는지 아닌지를 체크하는 방법은 다음과 같다.

 

1. 자신보다 작은 수가 몇 개인지를 구함

 

2. 자신과 같은 수가 몇 개인지를 구함

 

3. 자신보다 작은 수가 k개 미만, 같은 수 더한 값이 k개 이상 -> 정답!!!!
   자신보다 작은 수가 k개 이상이다 -> mid를 줄여야 됨
   else mid 늘려야 됨

 

자신보다 작은 수와 같은 수를 구하는 것에는 O(n) 시간이면 충분했다.

 

어차피 각각의 행이 행 번호의 배수들로 이루어져 있으므로

 

자신보다 작다 ->

1) 만약 mid값이 각 행의 마지막 원소보다 크다면 행의 모든 원소들은 mid값보다 작음!

2) 그렇지 않다면 나머지 연산을 통해 구할 수 있음! (코드로 이해하는 게 빠를 거예요)

 

자신과 같다 -> mid값을 행의 번호로 나누었을 때 0 이여야 함!

 

말로 써놓으니 굉장히 복잡해 보이지만 문제의 조건을 하나하나 맞춰가면서 구현하니 어렵진 않았다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
 
int main() {
    ll n, k;
    cin >> n >> k;
    ll l = 0, r = n * n;
    while (l <= r) {
        ll mid = (l + r) / 2;
        ll small = 0, same = 0;
        for (ll i = 1; i <= n; i++) {
            // 자신과 같은 수
            if (mid <= n*i && mid % i == 0) same++;
            // 자신보다 작은 수
            if (n * i < mid) small += n;
            else { 
                small += mid / i;
                if (mid % i == 0) small -= 1; 
            }
        }
        if (small < k && same + small >= k) { // 정답이 될 수 있는 조건
            cout << mid << "\n";
            break;
        }
        if (small >= k) r = mid - 1;
        else l = mid + 1;
    }
}

 

나는 right 값을 n*n으로 잡고 풀어서 맞았는데 다른 사람들은 어떻게 풀었는지 궁금해서 찾아보니 다들 k로 잡고 풀었다고 한다..

 

왜 k로 잡아도 되는지는 잘 모르겠지만? 

 

n제곱으로 잡고 풀어도 시간 복잡도가 충분하다는 것을 알았기 때문에 뭐... 넘어가자^^