[c++] 백준 1300 - K번째 수(이진 탐색)

 

0. [c++] 백준  -

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

1. 풀이

이번 문제는 꽤나 괜찮은 이진탐색 문제라고 생각한다.

문제에서 배열을 만들어 오름차순 정렬한 후 K번째의 원소를 구하는 과정을 실제로 해보았는데, 데이터 초과로 문제를 해결할 수 없었다.

그래서 이진 탐색을 활용하는 방법을 생각해보았다. 이번 활용에서 핵심이 되는 key는 1과 K사이를 탐색하는 것이었다.

기본적으로 k번째 원소는 K보다 같거나 작을 수 밖에 없는 구조로 이루어져 있다. 범위를 이렇게 잡고, mid를 활용해서,  

k번째 원소가 mid라 가정하면, mid가 나올 때 까지 몇개의 원소가 등장하는지 체크하고, 이걸 기준으로 first와 last를 수정해준다.

중간에 for문이 들어가는데, 이 활용은 각 층에 몇개의 원소가 mid보다 작거나 같은지 체크하는 부분이라 생각하면 된다.

N=3이라 생각하고 문제를 풀어보자.

3 6 9

2 4 6     라는 배열이 나오게 될 것인데, 6을 기준으로 for 문을 돌려보면, 3, 3, 2라는 cnt가 구해진다, 이때 3, 3, 2는 각 

1 2 3     층에서 6 이하의 원소 수라 보면 된다.

2. 소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
void binarySearch(const int & N, const int & K) {
    int first = 1;
    int last = K;
    int mid = 1;
    int ret;
    while (first <= last) {
        int cnt = 0;
        mid = (first + last) / 2;
        for (int i = 1; i <= N; i++)
            cnt += min(mid / i, N);
        if (cnt < K)
            first = mid + 1;
        else {
            ret = mid;
            last = mid - 1;
        }
    }
    cout << ret;
    return;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int N, K;
    cin >> N >> K;
 
    binarySearch(N, K);
 
 
}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!