[백준]1300: K번째 수 - JAVA

[백준]1300: K번째 수

풀이

이분탐색 문제이다. 문제의 조건에 따라 직접 배열을 만들고, 정렬하는 것도 방법 중 하나이겠지만 입력 조건에 N은 10의 5제곱 이기 때문에 이를 2차원 배열로 만들면 메모리 소비와 시간도 엄청 걸릴 것 이다. 그러므로 이분탐색으로 풀어야 한다.

 

문제의 예제입력을 푸는 과정을 살펴보자. 배열 A를 2차원 배열로 표현하면 다음과 같다.

 

배열A

1	2	3
2	4	6
3	6	9

 

이때, 6이라는 숫자가 오름차순 정렬되었을때 몇 번째에 오는지 알아보자. 

• 1번열은 모두 6이하 이므로 3을 더해준다.
• 2번열은 모두 6이하 이므로 3을 더해준다.
• 3번열은 3, 6 두개의 숫자가 6이하 이므로 2를 더해준다.

 

즉, 6은 8번째에 오는 숫자가 된다. 진짜인지 확인해 보자. A를 오름차순 정렬하면 다음과 같다.

인덱스	숫자
1	1
2	2
3	2
4	3
5	3
6	4
7	6
8	6
9	9

그럼 6이 몇번째에 오는지 알아내는 부분을 식으로 한번 표현해보자.

 

우선 배열A의 마지막 열은 3, 6, 9가 되며 이는 3의 배수가 된다. 이때 N은 3이므로 최대 수는 9가 된다. 그렇다면, 우리가 구하고자 하는 숫자6을 각 열의 인덱스로 나누면 해당 열에서 숫자6보다 작은 수의 개수를 구할 수 있다.

• 첫 번째 열(1, 2, 3)은 1의 배수이다. 해당 열에서 표현할 수 있는 6이하의 최대 수는 6개이다. (6/1=6)
• 두 번째 열(2, 4, 6)은 2의 배수이다. 해당 열에서 표현할 수 있는 6이하의 최대 수는 3개이다. (6/2=3)
• 세 번째 열(3, 6, 9)은 3의 배수이다. 해당 열에서 표현할 수 있는 6이하의 최대 수는 2개이다. (6/3=2)

 

위와 같은 경우일때, 배열의 크기는 3X3이다. 즉 첫 번째 열의 경우 1의 배수 중에서 6이하의 수는 6개가 되지만 열의 크기는 3이므로 첫 번째 열에서 6이하의 최대수는 3이된다.

 

이와 같은 방법을 식으로 나타내면 다음과 같다.

• i열에서 num이하의 개수 = num/i와 n 중에 더 작은값. = Math.min(num / i, n)

이 식을 이용하여 이분탐색을 진행하면 된다.

 

코드

import java.util.*;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int k = scan.nextInt();
        
        int l = 1;
        int r = k;
        int result = 0;
        while(l <= r) {
            int mid = (l + r) / 2;
            long count = 0;
            
            for(int i = 1; i <= n; i++) {
                count += Math.min(mid / i, n);
            }
            
            if(count < k) {
                l = mid + 1;
            } else {
                r = mid - 1;
                result = mid;
            }
        }
        System.out.println(result);
    }
}