[백준 1300] K번째 수 (JAVA)

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

1300번: K번째 수

 

일차원배열에 이차원배열의 값들을 넣고 sort하는 방식으로 접근했더니 역시나 10억이 넘기에 메모리 초과였다,,

 

1. 이분탐색으로, mid을 z번째 숫자라고 생각한다.

2. 줄마다 mid보다 작은 값이 몇개 있는지 확인한다. 즉, Math.min(mid / i번째 줄 , n)의 값을 모두 더한다.

3. 모두 더한 값이 k와  같을 경우-> result는 mid 이다!  

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class test1300 {

	static int result=0;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n= Integer.parseInt(br.readLine());
		int k= Integer.parseInt(br.readLine());
		
		find(n,k);
		System.out.println(result);
	}

	static void find(int n,int k) {
		int left=1;
		int end=k;
		while(left<=end) {
			int mid = (left+end)/2;
			
			int count=0;
			for(int i=1;i<n+1;i++) {
				count+=Math.min(mid/i, n);
			}
			
			if(count<k)
				left=mid+1;
			else {
				result=mid;
				end=mid-1;
			}
		}
	}
}