[ 백준 1300 ] K번째 수(Python)

문제
https://www.acmicpc.net/problem/1300

문제는 이러하다.
nxn 크기의 배열 a의 a[i][j] = i x j 일때,
a 배열의 모든 값들을 일차원 배열 b 에 넣고, 오름차순 했을 때 k번째에 위치한 b[k] 를 구하면 된다.

Solution

해당 문제는 이분탐색 문제이니,
start의 값을 1, end 값을 k로 초기화하고, 먼저 k보다 작은 수의 곱이 몇개인지 찾으면 된다.
k보다 작은 수가 몇개인지 찾아내면 k가 몇번째 숫자인지 알아낼 수 있기 때문이다.

코드의 mid 는 b 리스트를 일렬로 나열했을 때, cnt번째 값을 나타낸다.
즉, a 배열에서 mid 보다 작은 값의 개수가 cnt개인 것이다.

1. cnt 구하기

while start <= end:
    mid = (start+end) // 2
    cnt = 0

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

예를 들어 10 10에서 20보다 작거나 같은 수를 생각해보자.
1X1~1X10
21~210
31~3*6
.
.
.
10x1~10x2
위 수가 존재할텐데, 이는 반대로 생각해보면 20을 행으로 나눈 몫이다.
20//1: 10개 --> 단 열의 숫자(NxN배열이므로)를 초과할 수 없다.
20//2: 10개
20//3: 6개
.
.
20//10: 2개
따라서 이를 식으로 표기해보면 위와 같다.

코드

N, K = int(input()), int(input())
start, end = 1, K

while start <= end:
    mid = (start + end) // 2
    
    temp = 0
    for i in range(1, N+1):
        temp += min(mid//i, N) #mid 이하의 i의 배수 or 최대 N
    
    if temp >= K: 
        answer = mid
        end = mid - 1
    else:
        start = mid + 1
print(answer)