[백준 - 1300] K번째 수 .java

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

(이 문제는 도움을 받았다)

 

<문제 분석>

k의 범위가 n의 2승인데 n이 10의 5승보다 작거나 같기 때문에 시간 복잡도가 n^2인 알고리즘을 사용할 수 없다.

-> 이진 탐색 사용 

-> 중앙값보다 작은 수의 개수를 세면서 범위를 절반씩 줄이는 방법으로 b[k]를 구한다.

 

푸는 결정적인 아이디어를 도움받았다.

(참고 책/  do it! 알고리즘 코딩테스트 - 자바편)

 

• 2차원 배열: n행이 n의 배수로 구성
• 2차원 배열의 k번째 수는 k를 넘지 않는다. -> k보다 작은 수의 개수를 세는것이 포인트
• 애초에 이진탐색을 생각하는게 어려운 문제였다.
• start = 시작
• end = 찾는 값 = k
• 각 행에서 mid보다 작거나 같은 수의 개수: mid / 각행의 첫번째 값
• math.min(mid/i, n) : mid보다 작거나 같은 수의 개수 
• mid보다 작은 수의 개수 < k: start = mid +1
• mid보다 작은 수의 개수 >= k : end = mid -1, 정답을 mid로 업데이트 
• start가 end보다 커지면 종료 -> 정답 출력

 

괜히 골드 1이 아니다.. 코드만 보면 간단하지만 이 문제에서 이진탐색을 떠올리고 mid값이 몇번째 값인지 k보다 작은 수를 세는 계산식을 세우는것이 어려웠다.. 처음엔 힌트를 봐도 몰랐다..

import java.util.*;

public class Main {
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        // 입력 받아 저장
        int n = sc.nextInt();
        int k = sc.nextInt();

        long start = 1;
        long end = k;
        long answer = 0;

        //이진탐색
        while (start <= end) {
            long mid = (start + end) / 2;
            long count = 0;

            //중앙값보다 작거나 같은 수의 개수 구하기
            for(int i = 1; i <= n; i++) {
                count += Math.min(mid/i, n);
            }
            if(count < k) {
                start = mid + 1;
            } else{
                end = mid - 1;
            }
            
        }
        System.out.println(start);


    }

}