[이진탐색] 백준 1300번

문제

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.
배열 A와 B의 인덱스는 1부터 시작한다.

 

문제분석

첫째 줄에 배열의 크기 N이 주어진다. N은 10^5보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다.
k는 min(10^9, N^2)보다 작거나 같은 자연수이다.

• 10^5 이므로, O(N^2)으로 풀이를 할 경우 메모리 초과가 나온다.
• 이진탐색을 이용하여 풀이를 할 생각을 해야한다. (O(logN))

3*3 예시)

• 3 * 3 배열 형성 (N = 3)
• K 값 : 7

[i]/[j] (인덱스)	1	2	3	결과
1	1	2	3	-> 1의 배수
2	2	4	6	-> 2의 배수
3	3	6	9	-> 3의 배수

K값은 7이므로, A배열을 B배열로 옮겼을 때 오름차순으로 정렬되므로
{1,2,2,3,3,4,6,6,9}로 정렬되므로, 결과는 6이된다

K값보다 낮은수들이 앞쪽에 분포하므로, 각 배열의 행에서 K값보다 앞서는 수들의 개수를 찾으면 된다

 

문제풀이

[핵심]
찾는값 > 행들의 합 : start = middle +1;
찾는값 <= 행들의 합 : end = middle -1; (result값 저장 = middle)
----------------------------------------------------------------------------
middle = 1(첫번째 인덱스) + 7(찾는 값)  / 2 

첫번째 행)
"1의 배수"
- middle(4) / 1 = 4 (한 행의 개수 최대 개수는 3이므로, 4->3)
두번째 행)
"2의 배수"
- k(4) /2 =  2
세번째 행)
"3의 배수"
- k(4) / 3 = 1

[이진탐색]
"찾는 값 (7) > 6 (첫번째행 + 두번째행 + 세번째행)" :  start = middle +1;
(진행...)
----------------------------------------------------------------------------

 

슈도코드

N (배열크기)
K (찾는 값)
start(시작 인덱스 초기화)
end (찾는 값)
result (선언)

while(start <= end){
    int middle = (start + end) /2;
    int sum = 0;
    for(행의 개수만큼){
        count = middle/i; (행에서 K값보다 작아서 포함되는 수의 개수)
        if (count가 행의 최대개수가 넘으면)
            count = 행의 최대 개수
        sum += count; (행에서 K값보다 작은 수들의 개수)
    }
    
    if( 찾는 값 <= sum){
        end = middle - 1;
        result = middle;
    }else{
        start = middle + 1;
   }
}

result값 출력

 

 

구현

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class App {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int arrSize = Integer.parseInt(bf.readLine());
        int findNum = Integer.parseInt(bf.readLine());
        int start = 1;
        int end = findNum;
        int result = 0;
        while(start <= end){
            int middle = (start + end) / 2;
            int sum = 0;
            int count = 0;
            for (int i = 1; i < arrSize+1; i++){
                count = middle/i;
                if (count > arrSize){
                    count = arrSize;
                }
                sum += count;
            }

            
            if ( findNum <= sum){
                end = middle - 1;
                result = middle;
            }else{
                start = middle + 1;
            }
        }
        System.out.println(result);

    }
}