[알고리즘] 1300 k번째 수

🗒️ 문제 : 백준 1300 k번째 수

📎 분류 : binary search

2차원 배열의 값들은 i * j이다.

1차원 배열의 값은 2차원 배열을 오름차순으로 정렬한 것이다.

2차원 배열과 1차원 배열의 인덱스는 1부터 시작한다.

• 2차원 배열을 만들게 되면 N의 크기가 커서 시간초과 발생

접근 방식

3x3 2차원 배열의 경우

{

{1,2,3},

{2,4,6},

{3,6,9}

}

B[6] 은 얼마일까? 

B[] = {1,2,2,3,3,4,6,6,9} 이므로, 4 이다.

이는 2차원 배열을 1차원 배열로 늘여뜨려놓은 걸 수도 있지만,

1단 2단 3단

1     2    3

2     4    6

3     6    9

각 단에서 4보다 작은 수의 개수를 다 더한 값과 같다.

단이 i부터 n까지면,

min ( 4/1 , 3 ) + 4/ 2 + 4/3 = 3 + 2 + 1 = 6

 

즉, B[k] = x 의 의미는 x보다 작은 수의 개수의 합이 k이면 된다.

x의 값은 1부터 n*n까지 가능하고, 더 줄이게 된다면 

k값이 x값의 최대이므로, (k값보다 더 작은 수를 중복해서 B배열에 놓을 수 있다)

1 <= x <= k 가 된다.

---

코드

package 알고리즘_코딩테스트.dayone.mar03;

import java.util.*;
import java.io.*;

public class BOJ_1300 {
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static int n, k;
    static int[] oneline;

    public static void main(String[] args) throws IOException{
        //n, k 입력 받기
        n = Integer.parseInt(bf.readLine());
        k = Integer.parseInt(bf.readLine());
        long low = 1;
        long high = (long) n*n;


        //B[k] = x 이면, x보다 작은 수가 최소 k개  1 2 2 3 4 4 5 6
        //이분탐색
        while(low <= high){
            long x = (low + high) / 2; //임의의 long x
            long count = 0;
            for (int i = 1 ; i <= n; i++){
                count += Math.min(x / i , n);
            }
            if (count < k){
                low = x + 1;
            }else{
                high = x - 1;
            }
        }

        System.out.println(low);



    }
}

위 코드에서 

count 값 (임의로 정한 x값보다 작은 수의 개수) 이 k보다 작으면, x값을 더 키워야하므로,

low = x + 1

count 값이 k보다 크면, x값을 더 작게해야하므로,

high = x - 1

로 조정해야한다.