1300. K번째 수

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

1300번: K번째 수

 

 

티어 : 골드2

 

약간의 수학적 규칙성? 과 이진 탐색을 이용해서 해결했다.

 

다 풀고 나서 다른 사람들의 풀이를 구경했는데 나와 같은 방법으로 해결한 사람이 많이 보여서

왠지 모르게 기분이 좋았다.

 

#include<stdio.h>

#define MAX 1000000000

int n, k;

int min(int x, int y){
    if(x < y) return x;
    return y;
}

int f(int left, int right){
    
    int mid = (left + right)/2;
    long long int sum=0;
    for(int i=1 ; i<=n ; i++) sum += min(mid/i, n);

    if(right == left+1){
         if(sum >= k) return left;
         else return right;
    }

    if(sum >= k) return f(left, mid);
    else return f(mid, right);
}

int main()
{
    scanf("%d %d", &n, &k);
    printf("%d", f(0, MAX));
}