백준 1300 K번째 수

K번째 수 성공분류

 

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

128 MB

13330

4740

3472

38.079%

문제

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다.

출력

B[k]를 출력한다.

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

int n;
int k;
int main() {
    cin >> n >> k;

    int first = 1, end = k;

    int result = -1;

    while (first <= end) {

        int sum = 0;

        int mid = (first + end) / 2;

        for (int i = 1; i <= n; i++){
            sum += min(mid / i, n);
		}
        if (cnt < k){
            first = mid + 1;
        }else {
            result = mid;
            end = mid - 1;
        }
    }

    cout << result << "\n";

    return 0;
}

이분탐색인걸 알면서도 일단 브루트포스로 밀었으나 당연히 초과가 나서 이분탐색을 어느 부분에 도입할지를 고민하기 시작했다.

현재 원소의 인덱스를 구해 k와 비교하며 이분 탐색을 수행한다.
인덱스를 구하는 방법은 mid를 골라 mid보다 작은 숫자의 개수를 파악해서 K 번째 숫자를 구한다.

작은 숫자들의 갯수를 누적하며 값이 k보다 작은지를 파악해 k보다 크거나 같다면 result에 현재 인덱스(mid)를 저장하고 범위의 가장 끝(end)값을 mid-1로 두어 다시 해당 로직을 반복한다.

반대로 cnt가 k보다 작다면 first값을 mid+1로 두어 로직을 반복해 cnt갯수를 채워준다.

예를 들어, 5 * 5 행렬에서 8보다 작거나 같은 수의 개수를 구한다면

1 2 3 4 5    
2 4 6 8 10   
3 6 9 12 15  
4 8 12 16 20 
5 10 15 20 25

따라서 위와 같이 8보다 작거나 같은 수의 개수를 구하면 14가 되고, 이것이 8의 인덱스가 된다.