Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

21. 이분 탐색

이분 탐색 알고리즘을 배워 봅시다.

Java / Python

6. K번째 수

1300번

의외로 이분 탐색으로 풀 수 있는 놀라운 문제 1

이번 문제는 크기가 NxN인 배열 A에 들어있는 수 (A[i][j] = ixj)를 일차원 배열 B(NxN)에 넣어 B를 오름파순 정렬했을 때 B[k]를 구하는 문제입니다. 첫째 줄에 배열의 크기 N이 주어지고, N은 105보다 작거나 같은 자연수입니다. 둘째 줄에는 k가 주어지고 k는 min(10^9, N^2)보다 작거나 같은 자연수입니다.

• Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
		int N = Integer.parseInt(br.readLine());
		int K = Integer.parseInt(br.readLine());

		long left = 1; 
		long right = K;
		long result = 0;
        
		while (left <= right) {
			long mid = (left + right) / 2;
			long cnt = 0;
            
			// mid >= 인 수 계산
			for (int i = 1; i <= N ; i++) { 
				cnt += Math.min(mid / i, N);
			}
			if (cnt < K) { 
				left = mid + 1;
			} else {
				result = mid;
				right = mid - 1;
			}
		}
		bw.write(result + "\n");
		br.close();
		bw.flush();
		bw.close();
	}
}

• Python

import sys
N, K = int(sys.stdin.readline()), int(sys.stdin.readline())

left = 1
right = K
result = 0

while left <= right: 
    mid = (left + right) // 2 
    cnt = 0
    for i in range(1, N+1):
        cnt += min(mid // i, N)
    if cnt < K:
        left = mid + 1
    else:
        result = mid
        right = mid - 1
print(result)