[백준 1300] k번째수

문제풀이

이분 탐색을 공부하려고 푼 문제인데 특정 공식을 알지 못해 전혀 접근 조차 못했다. 

배열안에 값이 i*j일때 인덱스를 구하는 방법은

해당 수를 각 열으로 나눠 몫수가 그 열에서 8보다 작은 행의 개수이다. 

만약 몫>행의수 일 경우에 행의수를 반환

 

나머지는 이분탐색으로 찾는다 가장 작은수는 1 가장 큰수는 n*n임을 알수있기때문.

 

소스코드

 

 
#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
long long N;
long long k;
 
long long getMidIndex(long long mid){
    long long cnt=0;
    for (long long i=1;i<=N;i++){
        cnt+=min(N,mid/i);
    }
    return cnt;
}
int main() {
    scanf("%lld %lld",&N,&k);
 
    
    long long left =1, right = N*N;
    long long result=1;
    while(left<=right){
        long long mid = (left+right)/2;
        if(getMidIndex(mid)>=k){
            result = mid;
            right = mid -1;
        }
        else{
            left = mid +1;
        }
    }
    printf("%lld\n",result);
    
    return 0;
}
 

 

문제 링크 : https://www.acmicpc.net/problem/1300

1300번: K번째 수