[ACMICPC] 1300 . K번째 수

1300번 K번째 수

문제 보러가기

🅰 설계

1. 어떤 방법을 쓸 것인가?

• 문제에서 주어지는 k는 최대 10^9 = 10억이다. NxN 행렬을 만들어서 직접 정렬해보는 방법은 할 수 없다.
• B 행렬은 정렬되어 있다. 정렬된 상태에서 빠르게 답을 찾는 방법으로 이분 탐색을 생각해 볼 수 있다.

2. 이분 탐색을 어떻게 적용하는가?

• A 행렬에서 모든 행을 돌면서, 각 행에 x보다 작거나 같은 숫자를 카운트하여 그 개수가 k보다 작으면 답이 될 수 없고, k보다 크거나 같으면 답이 될 수 있다.
• 위 방법을 이분 탐색으로 구현하면 된다. 시간 복잡도는 행의 개수 N에 이분탐색 범위 log(N*N)을 곱해 O(N*log(N^2)) = O(2N*log(N))이 된다.

3. 전체 코드

import java.io.*;
import java.util.*;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    static long N,K;
    public static void main(String[] args) throws IOException {
        N = Long.parseLong(br.readLine());
        K = Long.parseLong(br.readLine());
 
        long l,r,mid;
        l = 0;
        r = N*N;
        while(l+1<r){
            mid = (l+r)/2; // mid보다 작거나 같은 수들의 개수를 센다
            long cnt = 0;
            for(int i=1;i<=N;i++){
                cnt += Math.min(N,mid/i); // 1 ... N행을 돌면서 mid보다 작거나 같은 수들의 개수를 센다
            }
            if(cnt < K){ // 현재 mid보다 작거나 같은 수의 개수 cnt가 K보다 작으면 현재 mid는 답이 될 수 없음
                l = mid;
            }else{ // 현재 mid보다 작거나 같은 수의 개수 cnt가 K보다 크거나 같으면 현재 mid는 답이 될 수 있음
                r = mid;
            }
        }
        System.out.println(r);
    }
}

✅ 후기

몇 번이나 다시 풀게된 문제지만, 아이디어 떠올리는 것이 굉장히 힘들다... 아이디어 떠올리는 게 전부인 문제였다.