[Java] 백준 1300: K번째 수

1. 문제

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

1300번: K번째 수

 

 

 

2. 풀이과정

 

1. mid보다 작거나 같은 값 개수 세기

 

n이 5이고 검사하는 값을 mid = 6이라고 할 때, 6보다 작거나 같은 값의 개수를 세는 법은 아래와 같다.

 

1*1, 1*2, 1*3, 1*4, 1*5

2*1, 2*2, 2*3, 2*4 ,2*5

3*1, 3*2, 3*3, 3*4, 3*5

4*1, 4*2, 4*3, 4*4, 4*5

5*1, 5*2, 5*3, 5*4, 5*5

 

6을 1~n으로 각각 나눈 값의 몫을 다 합하면 그 개수가 된다.

이 개수가 K와 같아도 더 작은 값을 찾는다는 말의 의미는, 위의 경우 mid=7인 경우 mid=6과 작거나 같은 값의 개수가 같지만, 위의 경우 7은 어떤 수의 곱으로 나올 수 없다. 경계에 있는 값을 구함으로써 값이 있다고 보장할 수 있는 것이다.

 

 

2. 이진 탐색의 범위가 1~K인 이유

 

예를 들어 설명해보자면, n = 3, k = 9일 때 9번째 수는 9이다.

1) n이 더 커지면 9번째 수는 유지되거나 작아진다.

          => 기존 값에서 여러 값이 추가되므로 9와 추가된 값들 중 최소를 찾음

2) n이 더 작아지면 9번째 수는 존재하지 않는다.

 

따라서, K번째 수가 가질 수 있는 가장 큰 값은 k개 이상의 수가 있는 n중 n이 가장 작은 값일 경우이다.

 

 

대각선에 없는 값일 경우도 마찬가지다. 보이지 않지만 대각선에 모든 자연수가 있다고 생각해보자. 설명은 아래 그림을 참고하고 결론적으로, 해당 영역의 K번째 수는 K보다 작다.

 

 

 

 

import java.util.Scanner;

public class Main {
	static int N, K;
	public static int binarySearch() {
		int left=1, right=K, mid;
		
		while(left <= right) {
			mid = (left+right)/2;//K번째 값 후보 선택
			
			long count = 0;//K보다 같거나 작은 수들의 개수 count
			for(int i=1;i<=N;i++) {//각 열에 K보다 같거나 작은 수들의 개수를 구해서 더해줌
				count += Math.min(mid/i, N);
			}
			
			if(count < K)//K개보다 적으면
				left = mid+1;//수를 더 크게 잡자
			else
				right = mid-1;//같아도 더 작은 수가 있을 수 있음
		}
		return left;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K = sc.nextInt();
		System.out.println(binarySearch());
	}
}