[백준 1300] K번째 수-Java

문제

백준 1300 번

문제 요약

문제를 이해하는데 한참 걸렸다.. 정리하자면 다음과 같다.

• 다음 그림처럼 N * N 크기의 배열을 1차원 배열로 오름차순으로 정렬 시켰을 때 (B 배열), 정렬 시킨 B 배열의 k 번째 값을 구하는 문제이다.

입출력 분석

3 // N의 값 입력
7 // k의 값 입력

제한 사항

• 시간 제한은 2초
• 메모리 제한은 128MB이다.
• 입력 제한 사항
  • N은 10^5보다 작거나 같은 자연수이다.
  • 둘째 줄에 k가 주어진다. k는 min(10^9, N^2)보다 작거나 같은 자연수이다.

  문제 설계

1. 만약 선형 탐색으로 모든 배열을 순회한다면 최악의 경우 N^10 번이나 탐색 해야한다.

   • 하지만 이때 B 배열은 오름차순으로 정렬되있다고 했으니 이분 탐색이 적절할거 같다.

2. 그러나 A 배열을 B 배열로 정렬시킬 수 있을까?
   2.1 B 배열 분석
   

   2.2 A 배열 분석
   

• A 배열의 특징은 각 행이 구구단 처럼 증가한다.
  

3. 그러면 다음 그림처럼 배열을 내가 직접 정렬하여 값을 찾을 필요 없이 기준값 보다 작은 값의 개수로 판별으로만 값을 도출할 수 있다.
   

니머지는 코드로 설명하겠다

Code

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());

        long lo = 1;
        long hi = k;

        while (lo < hi){
            long mid = (lo + hi) / 2;
            long count = 0;

            for (int i=1; i<=N; i++){
                count += Math.min(mid/i, N);
            }

            if (k<=count){
                hi = mid;
            }else{
                lo = mid+1;
            }
        }
        System.out.print(lo);
    }
}

• 직관적으로 𝑥의 초기 범위는 1 ~ N^2 이지만, K가 가질 수 있는 인덱스는 N2 안에서 한정되어 있고, K의 최댓값은 N^2 이랑 같기 때문에 반드시 𝑥 ≤ K 일 수 밖에 없다.
  • 정리하면 𝑥 의 범위를 1 ≤ 𝑥 ≤ K 로 좁힐 수 있다.
• 또한, 𝑥 보다 작은 원소의 개수는 최대 N개를 넘지 못한다.