[ 백준 1300 ] K번째 수 (c/c++)

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

 

 

[ 문제 요약 ]

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

 

 

[ 문제 풀이 ]

1. B[k]에 들어갈 숫자는 A배열의 수 중에서 k보다 작은 수의 숫자의 개수가 들어가게 된다.

2. 이분 탐색을 통해 하나의 숫자를 정하고 계속 작은 수의 개수를 세다가 최대값을 출력하면 된다.

 

 

[ 소스 코드 ]

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

int N, K;

int main() {
    cin >> N >> K;
    int  low = 1, high = K;
    while (low < high){
        int mid = (low + high) / 2, cnt = 0;
        for (int i=1; i<=N; i++) cnt += min(N, mid/i);
        if (cnt < K) low = mid + 1;
        else high = mid;
    }
    cout << high;
    return 0;
}

 

 

[ 주의할 점 ]

코드의 아이디어가 어려운 문제였다.