[ BOJ 백준 1300번 - K번째 수 ] 해설 및 코드

 

 

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

목적

N*N 크기의 배열 A가 있다. A[i][j]에 i*j를 채워 넣고, 원소를 정렬하여 1차원 배열 B에 넣는다. 이때 B의 K번째 원소를 구하라.

 

접근법

1. 이분탐색으로 원소를 정하고, 좌우 범위 이동은 원소 크기 이하의 모든 원소 개수를 기준으로 한다.

2. 모든 원소의 개수는 O(n)으로 구해주자.

#include<iostream>
#include<algorithm>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;
 
    int l = 1, r = k;
    while (l <= r) {
        int num = (l + r) / 2;
 
        long long cnt = 0;
        f(i, 1, n) cnt += min(n, num / i);
 
        if (cnt >= k) r = num - 1;
        else l = num + 1;
    }
    cout << l;
}

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.