백준 1300. k번째 수

문제 : 백준 1300. k번째 수

문제

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다.

출력

B[k]를 출력한다.

풀이

우선 문제 이해를 못했다. 요즘 문제 이해부터 못하는 게 많은 것 같다.
N x N 배열 A를 1차원 배열 B가 N x N 가 된다니
1차원 배열이라 해놓고 N x N 이라 해놓으니 헷갈렸다.
B는 1차원 배열이 맞고 길이가 N x N 이라고 생각하면 된다.

그리고 이제 문제 풀이
이분탐색에 있는 문제이니 이분탐색인건 알겠는데, 이거 나열해서 정렬하고 B[k]를 구하면 되나? 생각했다. 근데 이분탐색인데 이분탐색을 어디에 적용하지?

자, 문제에서 오름차순으로 정렬한 B에서 B[k]를 구하라고 했다. 이 말은 즉, B[k]보다 작거나 같은 수가 k개 존재한다는 말이 된다. 그러므로 우리는 임의의 숫자 x를 지정하고, 숫자 x보다 작거나 같은 수가 k개인지 확인해보면 된다.

여기까지 풀이를 보고 '오키오키 어떻게 접근하라는 건지는 알았어, 근데 x보다 작거나 같은 수의 개수를 어떻게 구해야하지?' 라고 생각했다.

입력 N을 이용하여 구한 배열A의 값은 다음과 같다.

무슨 특징을 찾을 수 있을까? 나는 직접 배열을 그리고도 숫자 순서에 포커스하여서 특징을 잡아내지 못했다.

1행부터 N행까지 구구단인 것이 보인다.

임의의 수를 x = 12 로 해보자.

각 행 i마다 12 이하의 수는

12 / i 의 몫이다.
1행 = 12
2행 = 6
3행 = 4
4행 = 3
5행 = 2

느헹? 1행이랑 2행은 값이 5개밖에 없는데 몫은 5를 초과하는데요?
몫이 n을 초과하는 경우에는 n을 개수로 적용해준다.

참고 풀이에서 잘 설명해주셔서 문제와 풀이를 이해하는데 도움이 되었다.

풀이 코드 python

n = int(input())
k = int(input())

start = 1
end = k # arr의 최대값은 k를 넘어갈 수 없음
# k의 최대값은 N^2 이고, n x n 차원 배열 A의 최대값도 N^2이므로
# k번째 위치한 x의 값은 k를 벗어날 수 없다.

while (start <= end):
    mid = (start + end) // 2
    cnt = 0 # k 이하의 수가 몇 개인지 판단할 변수

    for i in range(1, n + 1):
        cnt += min(mid // i, n)

    if cnt < k:
        start = mid + 1
    else:
        end = mid -1
for i in arr:
    print(i)
print(start)

풀이 코드 java

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

public class boj1300 {
    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[][] arr = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                arr[i][j] = i*j;
            }
        }

        /* 구해야하는 것! arr을 오름차순으로 정렬하였을 때 k번째 수를 구하시오,
        이차원 배열 arr을 오름차순 1차원 배열로 만들면 100,000 x 100,000번의 연산으로
        시간 초과가 발생한다.
        arr에서 k번째 수를 찾아야한다. 오름차순으로 k번째는 곧 arr[k]보다 작거나 같은 수가
        k개 존재한다는 것이다.
        그래서 임의의 x를 두고 x이하의 수가 몇개인지 세가면 된다.
        x이하의 수가 몇개인지는 어떻게 구하면 될까?
        arr을 살펴보면 값들이 구구단처럼 나열되어 있다.
        임의의 x를 n단으로 나누어 각 단마다 x이하의 수가 몇개인지 파악할 수 있다.
        나온 개수를 기반으로 x의 값을 줄이거나 키우는 이진탐색을 적용하여 값을 찾아나갈 수 있다.
         */
        int start = 1;
        int end = k; // 끝 값이 배열의 가장 마지막 값인 n x n이 아닌 이유는 n x n 의 범위가 k보다 항상 작거나 같기 때문이다.
        while (start <= end) {
            int x = (start + end) / 2;
            int cnt = 0;

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

            if (cnt < k) {
                start = x + 1;
            }
            else
                end = x - 1;
        }

        System.out.println(start);



    }
}