문제 이해

K * K = T값이 있다.
K에는 1 ~ N까지의 값이 들어올 수 있다.
그렇다면 자연스럽게 T의 개수는 중복 포함 N * N 개가 존재할 것이다.

이 N * N의 T를 오름차순 정렬한 배열이 B일 때, B[k]에는 어떤 값이 저장되어 있는지 출력하라

문제 풀이

문제 자체는 매우 간단하다.
먼저 Arrays.sort() 메서드를 활용해보았다. 어차피 N*N번의 계산은 단순한 곱이므로 빠르게 계산될 것이며, NlogN 정도면 괜찮지 않을까라고 생각했다. 하지만 메모리 초과가 뜨면서, 이 문제는 곱 계산을 할 필요가 없는 문제라는 것을 파악했다.

먼저 이 문제를 해결하기 어려웠던 이유는 내가 문제를 풀 때 배열은 "Index"가 중요한 자료구조라고 생각하고 있었기 때문이다.
하지만 이 문제를 풀기 위해서는, index는 거의 역할을 하지 않고 배열에 저장될 "값"이 중요하다.

만약 내가 T라는 값을 정했다고 가정하자.
그렇다면 2 * K 값들 중 T 이하의 값들은 총 몇개 존재할까?
2 * K <= T ⇒ K <= T / 2.
K는 1 이상의 자연수이므로 총 T/2개 존재한다는 것을 알 수 있다.

이를 확장시켜보자.

1 * K : T/1개 존재

2 * K : T/2개 존재

...

N * K : T/N개 존재

즉, T 이하의 총 원소 개수는 T/1 + T/2 + ... + T/N개가 될 것이다.
이는 B의 배열 중 T값을 가진 index 중 가장 큰 값을 의미한다.

따라서 우리는 T값을 적절히 조절해가며 정답을 도출해나가면 된다.
여기서 중요한 점이 몇가지 있다.

1. T / a는 N을 넘길 수 없다 : K는 총 N개 존재하므로, a * K의 개수 또한 a는 고정 수이므로 N개 존재할 것이다.
   즉, T/a가 N보다 크다면, 총 N개 존재하는 것으로 계산해야한다.

2. 정확한 index를 구할 필요는 없다 : 위에서 구한 방법으로 우리는 B[index] = T인 index 중 가장 큰 값을 구한다는 것을 알 수 있다.
   즉, T/1 + T/2+... + T/N이 문제에서 주어진 k보다 크거나 같기만 하다면 정답이 될 수 있다는 의미이다. 왜냐하면, index >= k라면 index는 중복된 값 중 최대 index를 의미하기 때문에 그보다 작은 index에 존재하는 중복값이 B[k]가 될 수 있기 때문이다.

(ex) 3 * 3 ⇒ 1 2 2 3 3 4 6 6 9 상황을 생각해보자.
위 방식을 사용하면 B[index] = 6인 Case를 고려할 때 index = 8이 나올 것이다.
즉, B[index] = 6인 상황 중 가장 큰 index가 8이라는 의미이기 때문에 B[1] ~ B[7]모두 6이 될 수 있는 가능성이 생긴 것이다.
6 6 6 6 6 6 6 6 9인 상황에도 우리는 index = 8로 구할 것이기 때문이다(계속해서 말하지만, 지정한 값 중 가장 오른쪽 index를 구한 것이다)

그렇다면 이렇게 생각할 수 있다. 이럴 경우 B[5] = 6으로 출력할 수도 있지 않을까?
실제로 B[5] = 3인데 말이다.

하지만 이는 절대 그렇지 않다.

이분 탐색을 통해 우리는 T 값을 계속해서 바꿔 나갈 것이다. 즉, 다음 T는 예를 들어 5로 변경될 수 있을 것이고, 이 상황에서는 index < k인 상황이기 때문에 무시해도 되는 상황이 되는 것이다.

위의 모든 설명들을 압축하면 아래와 같다.

1. 임의의 숫자 T를 지정한다.

2. T 이하의 숫자는 배열 B에서 총 pos = $\sum min(\frac{T}{i}, N)$

3. pos >= k
   정답이 될 수 있는 후보이다. T값을 가지는 index 중 가장 오른쪽(큰) index가 pos이기 때문에 k 또한 T를 가질 수 있는 가능성이 존재한다.(B[k] = B[pos] or B[k] < B[pos])
   pos < k
   정답이 될 수 없다. T값을 가지는 index 중 가장 오른쪽(큰) index가 pos이다. 하지만 이 pos보다 k가 크다는 것은 B[k]가 B[pos] 보다 크다는 것을 의미하며, 정답이 될 수 없다.(B[k] > B[pos])

4. pos >= k
   B[k]<B[pos]인 상황을 배제해 줘야 한다. 따라서 T값을 감소시켜 재확인할 필요가 있다. T 값을 감소시키기 위해서 right값을 바꿔준다.
   pos < k
   B[k] > B[pos]이기 때문에 T값을 증가시켜 pos >= K인 상황을 만들어줘야 한다. 따라서 left값을 바꿔준다

위에서 설명했던 내용을 바탕으로 이분탐색을 수행하면 된다.

코드

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

public class Main {
	static int N, K;

	static Boolean determination(long y) {
        // 문제 풀이에서 pos와 k값을 비교하는 과정
        // sum : pos의 역할
		long sum = 0;
		for(int i =1;i<=N;i++) {
			sum += Math.min(N, y/i);
		}
		return sum >= K;
        // sum >= K라는 것은 pos>=K라는 의미이고, 
        // 정답이 될 수 있는 가능성이 있으므로 True 반환
        // 반대의 경우, 정답이 될 수 없으므로 False 반환
	}
	
	static void bin_serach() {
		Long left = (long) 0;
		Long right = (long) N * N;
		long mid;
		Long ans = left;
		
		while(left <= right) {
			mid = (left+right)/2;
			
            // left, right값 변경은 문제 풀이 참조
			if(determination(mid)) {
                // 정답이 될 수 있는 상황
				ans = mid;
				right = mid - 1;
			}
			else {
				left = mid + 1;
			}
		}
		
		System.out.println(ans);
	}
	
	
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();

		N = sc.nextInt();
		K = sc.nextInt();
		
		bin_serach();
	}
	
	static class FastReader // 입력을 빨리 받기 위한 클래스
}

결과

• 4번째 메모리 초과 : B의 모든 배열 값을 구하려고 했었다
• 2,3번째 틀렸습니다 : k는 min$(10^9, N^2)$