[백준(Baekjoon)][자바(java)] 1300 : K번째 수 / 이분 탐색

 

www.acmicpc.net/problem/1300

1300번: K번째 수

 

예)

n = 3, k = 7

 

1.  브루트 포스   --> 메모리 초과

 

2.  이분 탐색

 

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), k = sc.nextInt(), i;
		sc.close();
		
		int left = 1, right = k, mid, ans = 0;  long cnt;
		while( left <= right ) {
			cnt = 0;
			mid = ( left + right ) / 2;
			for( i = 1; i <= n; i++ )
				cnt += Math.min( mid/i, n );  // mid보다 작은 j의 수( i*j <= mid )
			if( cnt < k )
				left = mid + 1;
			else {
				right = mid - 1;
				ans = mid;
			}
		}
        
		System.out.println( ans );

	}
}

 

 

-  각 i의 배수들 중에서 임의의 mid 값보다 작거나 같은 수의 개수( cnt )를 구함 
    ( i*j <= mid, j <= mid/i )  ( cnt += min( mid/i, n ) )

-  mid 값은 이분탐색으로 구함
    ( mid = (left + right) / 2 )  ( 초기 left = 1, right = k )

-  cnt가 k보다 작으면,
    ( left = mid + 1 )

-  cnt가 k보다 크면,
    ( right = mid - 1 )  ( ans = mid )