문제

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

해설

오름차순으로 정렬된 배열 B[7] = 6이라면 최소 B 배열에 10보다 작거나 같은 값은 11개가 있다는 의미다
즉 B[K] = V 는 V보다 작거나 같은 수는 배열 B 안에 11개가 있다는 말이 된다.

또한 문제에서 배열이 N*N이며 각 원소는 N*N이므로 이는 구구단을 암시하게 된다.
각 단마다 임의의 값보다 작은 원소의 갯수는

for(int i = 0; i < N; i++){
	value/i
}

를 통해 알 수 있으며 위 결과값들을 다 구하면 N단까지 value보다 작거나 같은 값들의 갯수를 구할 수 있다.

for(int i = 0; i < N; i++){
	cnt +=value/i
}

대신 해당 갯수는 문제에 주어진 N값보다 작아야 된다. 문제의 배열은N*N이므로 N이 3인데 value가 11이면 1단에서는 11이 나올거고 이는 N값보다 크게 되므로 틀리게 된다.

for(int i = 0; i < N; i++){
	cnt += Math.sort(value/i,N) //value값은 mid 값이며 mid 값 / 구구단을 통해 해당 구구단에서 mid값 보다 작은 값의 갯수를 구한다. 이는 2차원 배열의 인덱스 값보다 작아야 된다.
}

참고

처음 이진 탐색을 시작할 떄, 1~index가 탐색 범위가 된다. 탐새 범위의 중간 값보다 작거나 같은 값의 개수를 구하는 것에 이진탐색을 사용하는것이다.

코드

import java.util.*;
import java.io.*;

public class J1300 {
    public static void main(String[] args)throws IOException {
        BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));

        int array = Integer.parseInt(buffer.readLine());
        int index = Integer.parseInt(buffer.readLine());

        int start = 0;
        int end = index;
        
        int result = 0;
        int mid;
        
        while(start <= end) {
            int cnt = 0;
            mid = (start + end) / 2;
            for (int i = 1; i <= array; i++){
                cnt += Math.min(mid/i, array);
            }
            
            if(cnt < index){
                start = mid+1;
            }else{
                end = mid-1;
                result = mid;
            }

        }
        System.out.println(result);
    }
}