BOJ_1300_G2_K번째 수

이진탐색 문제는 문제의 규칙을 이해하고 어떻게 적용할 수 있는지를 찾는 것이 중요하다고 느꼈다.

===========================================
문제
세준이는 크기가 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]를 출력한다.

===========================================

처음 문제를 풀 때는 이진 탐색 대상이 N*N 배열을 만들었을 때 [1,1],[2,2], ... , [N,N] 칸에 있는 숫자인 줄 알았다.

필요한 칸의 노드가 몇 번째 대각선 사이에 있고 두 대각선을 찾았을 때 그 사이에 필요한 칸의 노드가 몇번째로 존재하는지 검사하면 값을 찾을 수 있으리라 생각했다.

대각선에 들어갈 수 있는 공식은 구하였으나 문제는

4와 9 사이에는 4 4 6 6 5 5 8 8 가 있는데 문제에서는 정렬을 한다고 했으니 4 4 5 5 6 6 8 8이 되어서 이 방법으로는 정렬된 값만을 탐색할 수 있는 이진탐색을 적용할 수 없었다.

몇 시간 고민했으나 풀이가 떠오르지 않아 솔루션을 보았다.

예시 그림

ex) K = 22일 때 arr[K] = 16

핵심 1-1. K번째 수(arr[k])는 K보다 무조건 작다.
핵심 1-2. K는 K번째 수보다 무조건 크다.
핵심 2. K아래에는 K보다 작은 수가 K-1개만큼 존재한다.

K보다 작은 수를 구하는 방법은 배열의 행 첫번째 자리로 K를 나눈 뒤 모두 합하는 것이다.

K = 22일 때 1행: 5, 2행: 5, 3행: 5, 4행: 5, 5행: 4 로 총 24개가 나온다.

K 아래에는 21개밖에 나올 수 없기 때문에 값을 낮춰서 다시 계산한다.

여기서 이진탐색의 개념을 적용할 수 있다.

left = 1, right = K = 22(핵심 1-2를 고려했을 때)로 이진탐색을 시작한다.
첫 mid값은 11이고 배열에서 11보다 작은 수는 17개이므로 21개가 안되기 때문에 left = mid+1로 변경한다.
left = 12, right = 22, mid = 17
17보다 작은 수는 22개이므로 21개보다 크기 때문에 right = mid-1로 해준다.

이것을 반복해서 left가 right보다 클 때까지 반복해주면 된다.

mid가 해당 값과 일치해도 끝까지 수행해주어야 하는 게, 이 배열은 대각선을 기준으로 대칭이므로 같은 숫자가 2개 이상 나오는 경우가 존재한다. 같은 수 끼리는 같은 값이 나오기 때문에 마지막까지 left, right를 좁히며 K번째 수를 구하면 된다.

import java.util.Scanner;

public class BOJ_1300_G2_K번째수 {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int N = s.nextInt();
		long K = s.nextInt();

		long left = 1;
		long right = K;
		long ans = 0;
		while (true) {
			if (left > right)
				break;
			long mid = (left + right) / 2;

			long cnt = 0;
			for (int i = 1; i <= N; i++) {
				cnt += Math.min(mid / i, N);
			}
			if (cnt >= K) {
				ans = mid;
				right = mid - 1;
			} else if (cnt < K) {
				left = mid + 1;
			}
		}
		System.out.println(ans);
	}
}