문제

이제 두 문제 풀어봤으니까 자신감이 붙었다가 사라졌다.
문제 자체가 어려운 건 아닌데, 시간 제한과 메모리 제한을 맞추려다 보니 이진 탐색으로 풀어야하고 이진 탐색을 문제에 어떻게 녹여야할지가 매번 어렵다.

문제 풀이

[1차 시도] - 메모리 초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());

        int[] arrB = new int[N*N];
        int index = 0;
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                arrB[index++] = i*j;
            }
        }
        Arrays.sort(arrB);
        System.out.println(arrB[k]);
    }
}

---

[2차 시도]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());
        
        long low = 1;
        long high = K;
        
        while(low < high) {
            long mid = (low + high) / 2;
            long count = 0;
            
            for(int i = 1; i <= N; i++) {
                count += Math.min(mid / i, N);
            }

            // count가 많다는 것은 임의의 x(mid)보다 작은 수가 B[K]보다 많다는 뜻
            if(K <= count) {
                high = mid;
            }
            else {
                low = mid + 1;
            }
        }

        System.out.println(low);
    }
}

이 블로그에서 아주 친절하게 설명해주셨다. 너무나도 생각해보지 못한 방향이라서 놀라웠다.
솔직히 몇 달 후에 다시 풀라고 하면 그때가서도 이런 생각을 못할 수도 있을 거 같지만! 여러 번 풀다보면 이런 사고도 가능하겠지 싶다!

부족한 부분

• 이진 탐색의 구현은 알겠는데, 어떻게 문제에 녹여낼지가 어렵다.
• 분명 이진 탐색을 안 쓰고도 풀 수 있는 문제지만, 이진 탐색을 쓰는 이유는 시간 제한과 메모리 제한 때문일 것이다. 이때 역으로 시간 제한과 메모리 제한을 보고 어떻게 이진 탐색임을 유추해내야할까?
• 저번 특강 때, 1초에 N이 몇이면 O(log N)이고 뭐 그런 것들이 있었는데 다시 한번 알아봐야겠다.
• 메모리 제한도 마찬가지로, 한 배열에 어느정도의 메모리를 차지하는지도 알아봐야 겠다.