[BOJ] 1300 : K번째 수 (Python3)

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

문제

세준이는 N*N크기의 배열을 만들었다. (배열의 방 번호는 1부터 시작한다.)

그 배열을 A라고 했을 때, 배열에 들어가는 수는 A[i][j] = i*j 이다.

세준이는 이 수를 일차원 배열 B에 넣으려고 한다. 그렇게 되면, B의 크기는 N*N이 될 것이다. 그러고 난 후에, B를 오름차순 정렬해서 k번째 원소를 구하려고 한다.

N이 주어졌을 때, k번째 원소를 구하는 프로그램을 작성하시오.

입력

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

출력

k번째 원소를 출력한다.

풀이

N*N 배열을 일차원 배열로 정렬했을 때, k번째 수를 구하는 문제.
임의의 숫자 x를 두고 x보다 작거나 같은 수의 개수가 k와 비슷할 때까지 이진 탐색을 한다.
그러면 x보다 작거나 같은 수의 개수를 어떻게 구하는가?
배열에 수가 i*j 로 들어있으므로 i행에 속한 숫자들은 모두 i의 배수.
때문에 x를 i로 나누어주고 그 몫이 i 행에서 x보다 작은 수의 개수가 된다.
다만 한 행에서 나올 수 있는 개수가 n보다 클 수 없기 때문에 x//i와 n 중 최솟값을 취해야 한다.

이렇게 x가 몇 번째 수인지를 구해 k보다 크고 가장 가까운 수를 답으로 한다.

소스코드

import sys
input = sys.stdin.readline

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

# mid 보다 작은 수의 개수를 return하는 함수
def numCount(mid):
    cnt = 0
    for i in range(1, n+1):
        cnt += min(mid//i, n)
    return cnt

def binarySearch(k):
    start = 1
    end = k
    while start <= end:
        mid = (start + end) // 2
        num = numCount(mid)
        if num < k:
            start = mid + 1
        elif num >= k:
            ans = mid
            end = mid - 1
    return ans

print(binarySearch(k))