[BOJ-1300] K번째 수

N이 최대 10^5 이므로 아래와같이 구해서는 TLE나 메모리 초과가 난다.

import java.util.Arrays; import java.util.Scanner; public class Sol1300 { //N이 100000이므로 TLE나 메모리 초과남 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); //배열의 크기 int K = sc.nextInt(); //k번째 int[][] A = new int[N+1][N+1]; int[] B = new int[(N*N)+1]; int m = 0; for(int i = 1; i <= N; i++){ for(int j = 1; j <= N; j++){ B[m++] = A[i][j] = i*j; } } Arrays.sort(B); System.out.println(B[K]); } } /* 입력 3 7 출력 6 */

그래서 이분탐색을 이용해보자!

문제에서 A[i][j] = i*j 라고 했으므로 A배열의 i행의 숫자들은 모두 i의 배수임. 이런 j값들의 갯수를 구하면 되고 곧 j 는 A[i][j]/i 임. A[i][j]값을 이분탐색으로 mid값으로 놓고 돌리면 된다.

그리고 N 이 1000일때는 mid값이 1000*1000/2로 50만으로 N값 10^5을 넘어갈 수 있으므로 

Math.min(mid/i, N) 으로 처리 해준다.

import java.util.Arrays; import java.util.Scanner; public class Sol1300_2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); //배열의 크기 int K = sc.nextInt(); //k번째 int left = 1; int right = K; int answer = 0; while(left <= right){ long cnt = 0; int mid = (left + right) / 2; for(int i = 1; i <= N; i++){ //N이 1000일땐 50만/i가 N넘어갈 수 있으므로 min(mid/i, N)처리 cnt += Math.min(mid/i, N);  } if(cnt < K){ left = mid + 1; } else{ answer = mid; right = mid - 1; } } System.out.println(answer); } } /* 입력 3 7 출력 6 */