백준 1300 - K번째 수 (파이썬)

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

풀이

1. 문제 조건
   • N×N 크기의 배열 A가 있음.
   • A[i][j] = i × j 로 채워져 있음.
   • 이 배열을 일차원 배열로 변환하고 정렬했을 때, K번째로 작은 수를 찾아야 함.
2. mid 값 기준으로 몇 개의 원소가 작은지 확인
   • mid 값보다 작거나 같은 원소 개수를 구해 count 값으로 활용.
   • 특정 수 X보다 작은 원소의 개수를 구하는 방법
   • A[i][j] = i * j 이므로 i번째 행에서 X 이하의 수 개수 = min(N, (X - 1) // i)
   • 모든 i (1~N)에 대해 누적하여 개수를 세면 된다.
3. K와 비교하여 mid 조정
   • count < K 이면 mid가 너무 작다는 뜻이므로 low를 증가.
   • count >= K 이면 mid가 충분히 크므로 high를 줄임.
4. 시간 복잡도 분석

• 이분 탐색의 탐색 범위: 1 ~ N*N → O(log(N^2)) = O(2 log N) = O(log N)
• 카운트 계산: O(N)
• 총 시간 복잡도: O(N log N)

코드

# 백준 1300 - K번째 수
# 분류 : 이분 탐색

N = int(input())
K = int(input())

low = 1
high = N * N
answer = -1

while low <= high :
    mid = (low + high) // 2

    count = 0
    for i in range(1, N + 1) :
        # i, 2 * i, 3 *i, ..., N * i
        count += min(N, (mid - 1) // i)
    
    if count < K :
        answer = mid
        low = mid + 1
    else :
        high = mid - 1

print(answer)