[백준] 1300번(Java)

📖 요세푸스 문제 0

[ 문제 ]
세준이는 크기가 $N×N$인 배열 $A$를 만들었다. 배열에 들어있는 수 $A[i][j] = i×j$ 이다. 이 수를 일차원 배열 $B$에 넣으면 $B$의 크기는 $N×N$이 된다. $B$를 오름차순 정렬했을 때, $B[k]$를 구해보자.
배열 $A$와 $B$의 인덱스는 1부터 시작한다.

💡풀이

• 처음엔 일반 배열을 만들어서 풀이했다. 당연하게도 메모리 초과가 났다.
• 문제의 조건은 배열을 생성하지 않고 $k$ 번째 수를 구하는 것.
• 조건을 바꾸어 직접 수를 계산하는 식으로 생각했으나 이것 또한 시간 초과가 났다.
• 풀이의 접근을 바꾸어 2차원 배열의 한 행에 들어있는 수들 중에서 임의로 지정한 수 $n$보다 작은 숫자들의 수를 구하기로 했다.
• 보통 $1×i$, $2×i$, $3×i$ ... 의 규칙으로 늘어나기 때문에, 이것보다 작은 수들의 개수는 임의의 수 $n$을 $i$로 나눈 몫이 된다.

package binary_search;

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

public class bj1300 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N, k;
    static long[][] A;
    static long[] B;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());

        long answer = 0;
        long low = 1;
        long hi = N * N;

        while(low < hi){
            long mid = (low + hi) / 2;

            if(counting(mid) < k){
                low = mid + 1;
            }
            else {
                hi = mid;
            }
        }

        System.out.println(low);
    }

    private static long counting(long n){
        long res = 0;
        for(int i = 1 ; i <= N ; i ++){
            res += Math.min(n/i, N);
        }
        return res;
    }
}

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