[BOJ] 1300 K번째 수 - JAVA

1. 문제

1300번: K번째 수

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

배열 A와 B의 인덱스는 1부터 시작한다.

---

2. 풀이

어떤 수 A의 앞에 숫자가 몇 갠지 알려면 1부터 N까지 한 줄씩 탐색하면서 몇 개가 A보다 같거나 작은지 세면 된다.

A가 17이라면 다음과 같다.

	1	2	3	4	5	count
1	1*1	1*2	1*3	1*4	1*5	Math.min(17/1,5) = 5
2	2*1	2*2	2*3	2*4	2*5	Math.min(17/2,5) = 5
3	3*1	3*2	3*3	3*4	3*5	Math.min(17/3,5) = 5
4	4*1	4*2	4*3	4*4	4*5	Math.min(17/4,5) = 4
5	5*1	5*2	5*3	5*4	5*5	Math.min(17/5,5) = 3

17보다 같거나 작은 수는 총 22개다. 

K가 18이라면 A가 17보다 작아야 한다. 

K가 24라면 A가 17보다 커야 한다.

 

이 원리로 이분탐색을 진행한다. 가장 작은 수는 1, 가장 큰 수는 N*N이다. N의 최댓값은 10^5까지이므로, low,mid,high의 범위는 long이어야 한다. cnt역시 N*N까지 늘어날 수 있기 때문에 long타입이다.

import java.io.*;

public class BOJ_1300_K번째수 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      int K = Integer.parseInt(in.readLine());

      long low = 1, high = N*(long)N+1;
      long mid, cnt;

      while(low<high){
         mid = (low+high)/2;
         cnt=0;
         for(int i=1;i<=N;i++){
            cnt+=Math.min(mid/i,N);
         }
         if(cnt>=K) high = mid;
         else low = mid+1;
      }

      System.out.println(high);
   }
}

---

3. 결과

cnt타입을 int로 둬서 한 번 틀렸다.

별개로 이 문제는 생각하는 데 오래걸려서 나중에 한 번 더 풀어봐야겠다.