백준 1300 - Java

 

import java.util.Scanner;

public class BJ1300 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();

        long low = 1;
        long high = K;

        //이분 탐색 시작
        while(low < high) {
            long mid = (low + high) / 2;
            long count = 0;

            for(int i = 1; i <= N; i++) {
                count += Math.min(mid / i, N);
            }

            if(K <= count) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        System.out.println(low);
    }
}

 

N X N 이라는 행렬 A가 B로 나열 될 때를 푸는 문제이다.

A[i][j]는 i×j이므로, midmidmid 이하의 숫자를 세는 로직은 다음과 같음:

• 각 행 i에서 mid 이하의 숫자는 mid/i 개.
• 단, 한 행의 숫자 수는 N개를 넘을 수 없으므로 Math.min(mid / i, N)를 사용.