[백준] 1300번 K번째 수 - Java

문제 링크

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

문제

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

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

입력

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

알고리즘: 이분 탐색

풀이

N이 3이라고 가정하면
배열 B는
1x1 2x1 3x1
1x2 2x2 3x2
1x3 2x3 3x3
이다.
여기서 3일 때 나올 수 있는 최댓값은 9(N제곱)이고, 최솟값은 1이다.
mid 값보다 작은 게 몇 개인지 count해서 cout값이 K보다 크면 max = mid - 1,
K보다 작으면 min = mid + 1 해주면 된다. 주의할 점은 mid값과 같은 값이 있다면 따로 count해서 cout <= K <= cout + (same_cout - 1)에 통과하는지 체크해줘야 한다.

mid 보다 작거나 같은 값을 어떻게 찾는지가 핵심인데, N이 최대 100000이고 그러면 1~ 100000범위로 for문을 실행했을 때 i가 1이면 1x1 ~ 1x100000 값 중 mid보다 작은 값을 cout하기 위해서 mid/i 값으로 mid가 몇 번째인지 알 수 있다. 같은 값은 (mid%i == 0 && mid/i <= N) 이 조건에 부합하면 같은 값이 존재한다는 뜻이다. 이런 식으로 i ~ N 범위를 체크하면 mid보다 작은 값, 같은 값을 N의 시간 복잡도로 찾을 수 있다.
총시간 복잡도는 N * log N 이다.

소스 코드

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

public class Main {
    static long N,K;
    static long ans;
    public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Long.parseLong(br.readLine());
      K = Long.parseLong(br.readLine());
      long min = 1;
      long max = N * N;
      while(true) {
          long mid = (min + max)/2;
          long cout = 1;
          long same_cout = 0;
          for(long i=1; i<=N; i++) {
              long n_cout = mid/i;
              if(n_cout > N) cout += N;
              else {
                  if(mid%i != 0) {
                      cout += n_cout;
                  } else {
                      same_cout += 1;
                      cout += n_cout - 1;
                  }
              }
          }
          if(cout == K) {
              ans = mid;
              break;
          } else if(cout <= K && K <= cout + same_cout - 1) {
              ans = mid;
              break;
          }
          if(cout < K) {
              min = mid + 1;
          } else if(cout > K) {
              max = mid - 1;
          }
      }
      long weight = N * N;
      for(int i=1; i<=N; i++) {
          long quo = ans/i;
          if((quo == N) && (ans%i == 0)) {
              weight = 0;
              break;
          } else if(quo < N) {
              if(ans%i == 0) {
                  weight = 0;
                  break;
              } else {
                  weight = Math.min(weight, (i-ans%i));
              }
          }
      }
      System.out.println(ans + weight);
    }
}