백준 1300) K번째 수

dev_minoflower·2022년 8월 10일

1300. K번째 수

- jdk version: java 11
- 분류: 이분탐색

출처: https://www.acmicpc.net/problem/1300

접근 방법

A[i][j] = i*j를 N*N 크기의 일차원 배열로 표현한 B를 오름차순으로 정렬했을 때, B[k]를 구하는 것이 문제의 요점이다.

N의 크기는 100,000이기 때문에 단순히 2차원 배열로 풀게 되면 NN = 100,000 100,000 = 100억이 되고 당연히 시간초과가 발생한다.

(A배열의 원소가 ixj인데다 1차원 배열로 표현하고 오름차순으로 정렬까지..?)

도저히 감이 안잡혀서 알고리즘 분류에 있는 키워드를 보니 이분탐색 문제였다. 하지만 어떻게 풀어야 할지 생각이 안 났고 결국 다른 사람이 푼 풀이를 참고했다.

`k번째`가 의미하는 것은?

주어진 원소들 중에서 B[k]보다 작거나 같은 수들이 존재한다는 것이다.

예를 들어 k번 째 원소가 6이라고 가정한다면 i=1(1,2,3), i=2(2,4,6), i=3(3,6), 총 8개가 B[k](=6)보다는 작거나 같다는 것이다.

B[k]보다 작거나 같은 원소가 8개라는 것은 k가 8이라는 말과 같다. 이렇게 해서 마치 오름차순으로 정렬된 배열에서 k번 째의 원소를 구할 수 있게 된다.

그렇다면 N * N 배열에서 B[k]보다 작거나 같은 원소를 어떻게 찾을 수 있을까?

위에서 설명한 예시를 그대로 인용해본다면 (B[k] = 6이라고 가정)

각 행마다 6보다 작거나 같은 원소는 6 / i 로 구할 수 있다.

i로 나눈 몫은 i의 배수 중에서 6보다 작거나 같은 원소의 개수가 되기 때문이다.

여기서 짚고 넘어가야 할 점은 i = 1일 때 6 / 1 = 6 이 되어야 맞다. 하지만 실제로 3개임을 알 수 있다. 그래서 Math.min(N, 원소 / i)를 통해 N개가 되는 경우를 대비한다.

이분탐색

앞선 예시와 같이 B[k]의 값에 따라 작거나 같은 원소의 개수가 바뀌게 되니 결국 B[k]에 대한 이분탐색을 진행하면 된다.

이분탐색을 도입하면 시간 복잡도는 어떻게 될까?

O(logN)(이분탐색) x O(N)(특정 수보다 작거나 같은 수의 개수를 찾기 위해 1부터 N까지 순차탐색) = O(N * logN)

100,000 * 5 = 500,000 으로 충분히 주어진 시간 안에 구할 수 있게 됐다.

int low = 1;
int high = k;

high가 k인 이유는 k가 최대일 때가 N x N이 되기 때문이다. (3*3인 배열에서는 총 9개의 원소를 가진다.) 하지만 N x N은 너무 크기 때문에 문제 조건에서 k = min(10^9, N x N)으로 설정했음을 알 수 있다.

int mid, cnt;
while (low + 1 < high) {
    mid = (low + high) / 2;
    cnt = 0;

    for (int i = 1; i <= N; i++) {
        cnt += Math.min(N, mid / i);
    }
}

mid 변수는 B[k]를 의미(B[k] <= k를 항상 만족하며 k를 찾는 것이 아닌 B[k]를 찾기 때문)하게 되고, cnt 변수는 mid보다 작거나 같은 원소의 개수를 센다.

참고) cnt의 자료형이 int인 이유

k의 범위가 min(10^9, NN), 즉 최대 10^9가 되어 mid의 최댓값은 (1+10^9)/2 = 500,000,000(5억)이다.

이 때, Math.min(N, mid / i)에서 mid / i = 500,000,000 / 100,000 = 5,000이 되고 N번 수행하면 100,000 5,000 = 5억이 되므로 int형 범위 내에 속하게 된다.

 if (cnt >= k) {
    high = mid;
} else {
    low = mid;
}

if(cnt >= k): k번 째보다 같거나 크면 high를 줄여야 정답에 근접해진다.

else: k번 째보다 작으면 low를 늘려야 정답에 근접해진다.

이로써 B[k]를 구할 수 있다.

소스 코드

import java.io.*;

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 low = 1;
        int high = k;
        int mid, cnt;
        while (low + 1 < high) {
            mid = (low + high) / 2;
            cnt = 0;

            for (int i = 1; i <= N; i++) {
                cnt += Math.min(N, mid / i);
            }

            if (cnt >= k) {
                high = mid;
            } else {
                low = mid;
            }
        }
        System.out.print(high);
    }
}