알고리즘 풀이(JAVA) - [이분 탐색] 백준 알고리즘-1300(K번째 수)
By on October 15, 2019
문제
문제 링크 : 이분탐색-K번째 수 https://www.acmicpc.net/problem/1300
풀이
-
이 문제는 어떻게 이분 탐색으로 접근을 해야 할지 아무리 머리를 굴려도 모르겠어서 문제 풀이를 좀 살펴 보고 이해를 해야 했다.
배열을 정렬 해서 K 번째 배열 값을 출력 하면 될 문제인데 … 이 문제가 어떻게 이분 탐색으로 되지???
-
풀이 시작
-
첫번째. 배열의 수는 A[i][j] = i*j 이기 때문에 j 는 i의 배수이다.
-
N = 3 일 경우 아래와 같은 배열을 만들 수 있다.
-
2차원 배열
[1, 2, 3] 1의 배수
[2, 4, 6] 2의 배수
[3, 6, 9] 3의 배수 -
1차원 배열
[1, 2, 2, 3, 3, 4, 6, 6, 9]
-
-
-
두번째. 배열을 탐색 하면서 mid 값 보다 작거나 같은 수의 갯수를 더한 값이 K 값보다 큰 수중에서 최소 값을 구하자.
-
예1) k = 4 인 경우.
-
mid = (1 + 4) / 2 = 2 인 경우
- i = 1. Math.min(mid / i, 3) 인 경우 1 번째 행은 mid 보다 작거나 같은 수가 [2] 개 이다.
- i = 2. Math.min(mid / i, 3) 인 경우 2 번째 행은 mid 보다 작거나 같은 수가 [1] 개 이다.
- i = 3. Math.min(mid / i, 3) 인 경우 3 번째 행은 mid 보다 작거나 같은 수가 [0] 개 이다.
- (2 + 1 + 0) = 3 은 4(K) 보다 작기 때문에 2(mid) 는 k 번째 수가 아니다.
-
mid = (2 + 4) / 2 = 3 인 경우
- i = 1. Math.min(mid / i, 3) 인 경우 1 번째 행은 mid 보다 작거나 같은 수가 [3] 개 이다.
- i = 2. Math.min(mid / i, 3) 인 경우 2 번째 행은 mid 보다 작거나 같은 수가 [1] 개 이다.
- i = 3. Math.min(mid / i, 3) 인 경우 3 번째 행은 mid 보다 작거나 같은 수가 [1] 개 이다.
- (3 + 1 + 1) = 5 은 4(k) 보다 크기 때문에 3(mid) 는 K 번째의 수가 될 수 있다.
-
탐색 종료 . 4(k) 번째 수는 3(mid) 이다.
-
-
예1) k = 6 인 경우.
-
mid = (1 + 6) / 2 = 3 인 경우
- i = 1. Math.min(mid / i, 3) 인 경우 1 번째 행은 mid 보다 작거나 같은 수가 [3] 개 이다.
- i = 2. Math.min(mid / i, 3) 인 경우 2 번째 행은 mid 보다 작거나 같은 수가 [1] 개 이다.
- i = 3. Math.min(mid / i, 3) 인 경우 3 번째 행은 mid 보다 작거나 같은 수가 [1] 개 이다.
- (3 + 1 + 1) 은 6(K) 보다 작기 때문에 3(mid) 는 k 번째 수가 아니다.
-
mid = (4 + 6) / 2 = 5 인 경우
- i = 1. Math.min(mid / i, 3) 인 경우 1 번째 행은 mid 보다 작거나 같은 수가 [3] 개 이다.
- i = 2. Math.min(mid / i, 3) 인 경우 2 번째 행은 mid 보다 작거나 같은 수가 [2] 개 이다.
- i = 3. Math.min(mid / i, 3) 인 경우 3 번째 행은 mid 보다 작거나 같은 수가 [1] 개 이다.
- (3 + 2 + 1) 은 6(k) 보다 크거나 같기 때문에 5(mid) 는 K 번째의 수가 될 수 있다.
-
mid = (4 + 5) / 2 = 4 인 경우
- i = 1. Math.min(mid / 1, 3) 인 경우 1 번째 행은 mid 보다 작거나 같은 수가 [3] 개 이다.
- i = 2. Math.min(mid / 2, 3) 인 경우 2 번째 행은 mid 보다 작거나 같은 수가 [2] 개 이다.
- i = 3. Math.min(mid / 3, 3) 인 경우 3 번째 행은 mid 보다 작거나 같은 수가 [1] 개 이다.
- (3 + 2 + 1) 은 6(k) 보다 크거나 같기 때문에 4(mid) 는 K 번째의 수가 될 수 있다.
-
탐색 종료 . 6(k) 번째 수는 최소 값인 4(mid) 이다.
-
-
-
소스
- K 번째의 수(1300)
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
public class Baekjoon_1300 {
private static int n = 0;
private static int k = 0;
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
k = scanner.nextInt();
long left = 1;
long right = k;
System.out.println(bSearch(left, right));
}
private static long result = 0 ;
private static long bSearch(long left, long right) {
int cnt = 0;
long mid = (left + right) / 2;
if(left > right) return result;
for(int i = 1; i <= n; i++) {
cnt += Math.min(mid/i, n);
}
if(k <= cnt) {
result = mid;
return bSearch(left, mid -1);
}else{
return bSearch(mid + 1, right);
}
}
}