[백준/Java] 1300 k번째 수

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

1300번: K번째 수

입력으로 주어지는 행 또는 열의 크기 N은 10^5  , 따라서 전체 행렬의 크기는 최대 10^10 으로, 10,000,000,000 (100억)이 된다.
이는 브루트-포스로 탐색하기에는 너무 오래걸린다는 뜻이다.

그러나 사실 위의 조건만 가지고 이 문제를 이분탐색 문제라고 생각하기는 어렵다.

문제에서 A와 B배열의 인덱스는 1부터 시작하는데, 예를 들어 B[7]=6이면 7번째의 수가 6이라는 뜻이다.

B배열은 오름차순으로 정렬되어 있으므로, 위 식을 분석하면  6과 "같거나, 작은 값"이 "최소" 7개라는 뜻이 된다.

따라서 우리가 구하는 것은 B[K] = 𝑥 에서 원소 값 𝑥 를 찾는 것이다. 그렇다면, 𝑥 의 값을 조정해나가면서 𝑥 보다 작거나 같은 원소의 개수가 K와 같으면 된다.

A행렬의 N*N의 값을 그려가면서 보면, 구구단처럼 행렬의 원소가 구성되어 있다 (원소의 값이 i*j이므로) . 여기서 힌트를 얻을 수 있는데, 6보다 같거나 작은 값을 구하고 싶으면 1단에서는 6/1 =6, 2단에서는 6/2=3, 3단에서는 6/3=2,,...이렇게 개수를 구할 수 있다.

구해야하는 값은 원소  x보다 작거나 같은 원소들의 개수이므로, 그냥 단을 늘려가면서 (1단, 2단..) 누적합이 B[K] = 𝑥에서의  K와 같은지확인하면 될거라 생각한다.

그래서 
for(int i = 1; i <= N; i++) {
count += mid / i; 
}

와 같은 방법으로 진행했으나 주의해야 할 점이 있는데, 𝑥≤ K 임을 기억하고 이를 탐색 범위에 반영해주어야 한다.

행렬이 4*4라 가정했을때 찾는값이 13이라면,  13/1=13, 13/2=6,.. 이렇게 개수가 나오는데 4*4행렬의 한 열의 개수는 4개이므로 , 열의 개수와 비교해 더 작은 값을 카운트 시켜야한다.

따라서 for문 안의 코드는

count += min(mid / i, N); 이 되어야 한다.

또 하나는,  Lower-Bound를 써주어야 한다는 것이다. UpperBound로 접근할 시에는 초과하는 첫번째 값을 찾게 되어 정답이 다르게 나올 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int K = Integer.parseInt(br.readLine());
		
		
		long lo = 1;
		long hi = K;
		
		// lower-bound
		while(lo < hi) {
			
			long mid = (lo + hi) / 2;	
			long count = 0;
			
			
			for(int i = 1; i <= N; i++) {
				count += Math.min(mid / i, N);
			}
			
			
			if(K <= count) {
				hi = mid;
			}
			else {
				lo = mid + 1;
			}
		}
		
		System.out.println(lo);
	}
}