문제 링크

성능 요약

메모리: 14324 KB, 시간: 124 ms

분류

이분 탐색, 매개 변수 탐색

제출 일자

2025년 2월 14일 02:39:46

문제 설명

세준이는 크기가 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)보다 작거나 같은 자연수이다.

출력

B[k]를 출력한다.

풀이

느낀점

• K인덱스가 해당 수보다 작거나 같은 수의 개수인 것까지는 접근을 했는데, 시간복잡도를 해결할 규칙을 찾지 못했다.
• 풀이를 참고해보니 못 풀만 했다.. 배웠으니 됐다. 복잡한 내용을 잘 정리해주신 분이 계셨다.
  참고링크
  

설계 : 2시간 고민 후 풀이 참고

• B(k)에서 k는 B(k)보다 작거나 같은 수의 개수를 나타낸다.
• 그러면 B(k)보다 작거나 같은 수의 개수를 어떻게 확인할 것인가? 그냥 브루트포스로 하면 시간초과가 뻔하다.
  • A배열의 모양을 보면 구구단과 같은 모양을 띤다.
  • 특정한 수 x에 대해 i단에서 x보다 작거나 같은 수의 개수는 min( x / i , 열 길이) 개 이다.
  • i를 1부터 min(x, 행 길이)까지 순회하며 x보다 작거나 같은 수의 개수를 모두 더해 k와 비교하며 B(k)값을 찾아나간다.
  • 이때 k와 같은 개수를 찾더라도 가장 작은 수를 찾아야 알맞은 답이 나온다.
    • ex) n = 2일때, {1, 2, 2, 4} 에서 3으로 탐색해도 개수가 3개지만, 2까지 탐색해봐야 정확한 값을 알 수 있다.

코드(Java)

• 구현 시간: 15분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: K번째 수_1300
 * Date: 2025.02.13
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int n;
	static int k;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());

        int answer = 0;

		int low = 1;
		int high = k;
		int mid;
		while (low <= high) {
			mid = (low + high) / 2;

			int cnt = getMinCnt(mid);
			if (cnt < k) low = mid + 1;
			else {
				answer = mid;
				// 개수가 일치해도 최적의 수를 찾기 위해서는 끝까지 줄여서 확인해야 함
//				if (cnt == k) break;
				high = mid - 1;
			}
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
		br.close();
	}

	public static int getMinCnt(int num) {
		int cntSum = 0;
		for (int i = 1; i <= num && i <= n; i++) {
			cntSum += Math.min(num / i, n);
		}
		return cntSum;
	}
}