[ BOJ 1300 ] K번째 수(Python)

문제

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

한 달 전에 풀었던 문젠데 진짜 기억이 1도 안난다.
그만큼 이해가 안되셨다는 거겠지~ 🤗

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

문제 풀이 (🔗 참고)

먼저 k보다 작은 수의 곱이 몇개인지 찾으면 된다.
k보다 작은 수가 몇개인지 찾아내면 k가 몇번째 숫자인지 알아낼 수 있기 때문이다.

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

1. 이분 탐색 범위 정하기

start, end = 0, k

k번째 수는 k보다 클 수 없기 때문에 최댓값으로 정해주었다.

2. cnt 구하기

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

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

ex) '10 x 10'에서 20 보다 작거나 같은 수는
1x1 ~ 1x10 = 10개
2x1 ~ 2x10 = 10개
3x1 ~ 3x6 = 6개
...
즉 (20 // 1) + (20 // 2) + (20 // 3) + ... + (20 // 10) 이다.
= ( k // 1 ) + ( k // 2 ) + ... ( k // n)

그런데 이 때 (20 // 1) 처럼 n보다 큰 경우가 존재한다.
따라서 최대 n을 갖도록 해준다. min(mid // i, n)

3. cnt 비교하기

if cnt >= k:
     answer = mid
     end = mid - 1
else:
     start = mid + 1

k보다 작은 수의 개수인 cnt가 k와 같거나 k보다 클 땐,
answer 변수에 mid를 넣어준다.

코드

import sys
input = sys.stdin.readline

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

start, end = 0, k
# k번째 수는 k보다 클 수 없음

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

    for i in range(1,n+1):
        cnt += min(mid//i, n)  
        
    # print("[cnt]:",cnt)   
    if cnt >= k:
        answer = mid
        end = mid - 1
    else:
        start = mid + 1

print(answer)