백준 1300 K번째 수

문제

문제

접근법

매개변수 탐색 문제이다. 하지만 문제만 읽어서는 어떻게 해야 범위의 중간값 mid를 설정해야 할지, mid값을 어떻게 탐색해야 할지 답답했다.

문제를 처음부터 읽어보자. 조건은 배열의 크기 N, 그리고 우리가 찾아야하는 일차원 배열 B의 k번째 값이다.

매개변수 탐색에서 중요한 점은.

• 우리가 찾아야 하는 값을 범위로 정해야 함. (= 그러므로 이 문제에서는 범위를 B[k]이 가능한 숫자의 범위로 설정해야 함.)
• 범위에서 중간값을 찾고, 이 값이 우리가 찾아야 하는 값보다 구했을 때 적은지, 큰지를 알아야 함 (그래야 범위를 조정할 수 있음)

핵심 아이디어

NxN인 2차원 배열 A가 있다고 해보자. 특정 범위에서 중간값인 mid = 107이 있다고 했을 때, N = 3, 5, 11인 경우를 모두 볼 것이다.

우리가 찾아야 하는건 mid값인 107이 k번째에 위치해 있는지를 보는 것이고.
그렇다면 존재할 수 있는 수들을 차근차근 합산해서, 배열 A에서 106까지의 숫자들이 총 몇개 있는지를 세면 우린 107이 위치할 수 있는 위치를 알게 되고, 그러므로 이 숫자가 우리가 원하는 위치 k에 비해 너무 큰지 아니면 너무 적은지를 알 수 있게된다!

• N = 3인 경우 : 2차원 배열의 첫 행(i=1)에서, 존재할 수 있는 숫자는 1, 2, 3이다.(N=3이므로) 두 번째 행(i=2)에서, 존재할 수 있는 숫자는 2, 4, 6이다. 세 번째 행에서(i=3), 존재할 수 있는 숫자는 3,6,9 이다. 즉 총 숫자는 9개이고 107은 N=3일때 아무리 못해도 10번째 이후에 존재하게 될 것이다. (숫자가 존재할 수 없다는 점은 넘어가야 한다. 왜냐하면 우리는 정확한 숫자를 찾는 게 아니라 이 숫자가 어느 위치에 있는지 범위를 구해야 하기 때문.)
• N = 5인 경우 : 2차원 배열의 첫 행(i=1)에서, 존재 할 수 있는 숫자는 1, 2, 3, 4, 5이다. 이런 식으로 i=5행에서 존재할 수 있는 숫자는 5, 10, 15, 20, 25 총 25개가 존재할 수 있다. 그러므로 107은 N=5일때 최소 26번째 이후에 존재한다는 사실을 알 수 있다.

여기까지 왔을때 무언가 규칙이 있다는 것을 알 수 있다. N=11의 경우에 명확하게 보이게 된다.

• N = 11인 경우 : i=9까지는 9, 18, ... 99 이므로 총 99개가 107 앞에 존재할 수 있게 된다. 하지만 i=10부터 문제가 생기기 시작한다. 10부터 100까지는 107보다 크지만, 마지막 열의 숫자 110은 107보다 크다... 그러므로 i=10행은 10개만큼 mid=107 앞에 존재할 수 있다.
  그리고 i=11의 경우는 더 크다. 11... 99까지 9개만큼 존재할 수 있고, 110부터는 107보다 크기 때문에, 11행에선 총 9개만큼 존재할 수 있게 된다. 그래서 107은 아무리 못해도 119번째 이후에 존재하게 된다.
  실제로는 107이란 숫자는 존재하지 않기 때문에 119번째의 숫자는 110이다.

여기서 규칙을 찾았나요?

저것을 하나하나 구한다는 것은 사실 불가능하다. 규칙을 찾아서 규칙대로 적용하는게 제일 빠른 방식이 되는데. 여기서 중요한 점은 더하는 것을 N번 만큼 한다는 것이다.
그렇다면 우린 특정한 mid값에 대해서 그 앞에 존재하는 숫자의 개수 count값을 구하는데, 이걸 for문으로 N번만 하면 된다는 것이고. 이게 K보다 작다면 mid값을 작게 하고, K보다 크거나 같다면 mid값을 크게 하는 식으로 조정을 하면 올바르게 범위를 찾아나갈 수 있다는 것이다.

규칙을 지금부터 설명하겠다. 예시와 함께. 조건은 위와 같다. mid = 107, N=11인 경우

• i = 1의 경우 1행에서 mid=107 앞에 존재하는 숫자의 개수는 Math.min(mid/1 , N)이 된다. N의 경우가 매우 커졌을때를 생각해본다면 위와 같은 수식이 나오는 이유를 직관적으로 알 수 있다. 만약 N=107이라면 1행이 mid값 앞에 존재하는 숫자의 개수는 107개일 것이다. 1... 107까지 있기 때문. N=11일때 11개만 존재하는 것이 i행에 N개만큼 곱해서 나온 숫자의 개수이기 때문이다.
• 그러므로 mid를 i만큼 나눈 숫자가 N보다 크다면 N이 되고, N보다 작다면 mid/i의 숫자가 mid앞에 존재하는 i행의 숫자 개수가 된다는 것이다. ex) 107/11 = 9.727272... = 9. 다르게 본다면 i행에서 mid값 앞에 존재할 수 있는 숫자는 mid값보다 작은 숫자들. 그러므로 mid/i가 된다.

이 규칙을 적용한 코드를 본다면

import java.io.*;
import java.util.*;
public class Main {
    static int N;
    static int k;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
        long start = 1, end = k;
        long mid = 0;
        while(start <= end) {
            mid = (start+end)/2;

            if(check(mid)) {
                start = mid+1;
            }else {
                end = mid-1;
            }
        }

        System.out.println(start);
    }

    public static boolean check(long m) {
        long count = 0;
        
        for(int i=1; i<=N; i++){
            count += Math.min(m/i,N);
        }

        if(count < k) {
            return true;
        }else {
            return false;
        }
    }
}

여기서 왜 end값을 k로 두어도 괜찮냐면, 우리가 원하는 k번째의 수는 아무리 못해도 k보다 작거나 같게 된다. 위에서 본것처럼 숫자가 커진다면 갭은 더더욱 커지게 되고, k가 적더라도 계산해 본다면 k엔 무조건 k보다 작거나 같은 숫자가 들어간다는 사실을 알 수 있다.
그러므로 시간복잡도를 위해서 저렇게 할 수 있고, count를 int형으로 두었을 때 오버플로우가 되는 경우를 막기 위해서, int형으로 범위를 잡고 구하고 싶을 때 저런 식으로 둘 수 있다.

결과는 아래와 같다.