boj-1300 K번째 수

1300번: K번째 수

 

 

 

 

 

 

풀이

---

도저히 문제를 이해할 수 없어 다른 분의 풀이를 참조해 풀었던 문제입니다. 전체 풀이 과정은 아래와 같은데요, 핵심 아이디어에 관해서만 간단하게 설명해보겠습니다. 우선 2차원 배열 A는 N X N 형태(N은 10^5 이하)이며, A에 들어갈 값들은 N^2개인데 이 값들이 1차원 배열 B에 오름차순으로 들어있습니다.

 

 

이 문제는 순차적인 탐색으로 풀면 시간초과가 나기 때문에 이분탐색을 사용해야 합니다. 구하고자 하는 숫자보다 작은 숫자의 개수가 각 행에 몇 개 존재하는지를 알아야 하는데요, 이를 위해 구하고자 하는 숫자를 각 행의 수로 나눠줘야 합니다.  

 

 

 

 

 

 

이를 말로 하면 잘 와닿지 않을 수 있는데요, 그림으로 보면 조금 더 직관적으로 알 수 있습니다. 즉 각 행을 n으로 나눠서 자신보다 작은 수들을 찾으면 됩니다. 아래에서 4보다 작은 수를 찾는경우 첫 행에는 4개, 두번째 행에는 3개, 세 번째 행에는 2개, 마지막 행에는 1개가 존재하는데요, 따라서 총 10개의 수가 4보다 작습니다. 이를 일반화해보면 우리가 구하려는 값이 S일때 이 S는 1행부터 N행까지 i번째 행에서 min(S/i, N)을 더한 값이라는 것을 알 수가 있습니다. 

 

 

 

 

 

 

따라서 우리는 1부터 K 사이에 있는 S값을 찾아야 하며 이 과정에서 이분탐색을 사용하여 문제를 풀 수가 있는 것입니다. 만약 어떤 S에 대해 1행부터 N행까지 i번째 행에서 min(S/i, N)을 더한 값이 K보다 작다면 S값을 더 큰 범위에서 찾아야 하며, K보다 크면 S값 이하에서 탐색을 해야하는 것입니다. 따라서 코드는 아래와 같습니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static long n;
    static long k;
    static long result;

    public static void main(String[] args) throws Exception {
        n = input.inputLong();
        k = input.inputLong();

        long left = 1;
        long right = k;

        System.out.println(binarySearch(left, right));
    }

    static long binarySearch(long left, long right) {
        int count = 0;
        if (left > right) return result;
        long mid = (left + right) / 2;

        for (int index = 1; index <= n; index++) {
            count += Math.min(mid / index, n);
        }

        if (k <= count) {
            result = mid;
            return binarySearch(left, mid - 1);
        }
        return binarySearch(mid+1, right);
    }

    static Input input = new Input();

    static class Input {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        public long inputLong() throws Exception {
            if (!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
            return Integer.parseInt(st.nextToken());
        }

        public int integer() throws Exception {
            if (!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
            return Integer.parseInt(st.nextToken());
        }

        public String next() throws Exception {
            if (!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
    }
}