[Algorithm][Python3][BOJ 1300] K번째 수

문제

 

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

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

 

배열 A

	1	2	3
1	1	2	3
2	2	4	6
3	3	6	9

배열 B

1

2

2

3

3

4

6

6

9

 

풀이

 

알고리즘 : 이분 탐색

k번째 수를 찾는 이분 탐색을 수행

- start = 1, end = k : k번째 수는 k보다 작거나 같음

- mid가 몇 번째 수인지 아는 방법 : mid보다 작거나 같은 숫자를 구하기

   -> i * j <= mid

   -> mid // i

       but mid // i 가 N보다 클 경우가 있으므로 min(mid // i, N)

 

Python 코드

 

import sys
input = sys.stdin.readline

N = int(input())
k = int(input())

answer = 0
start = 1
end = k

while (start <= end) :
    mid = (start + end) // 2
    n_min = 0
    for i in range(1, N+1) :
        n_min += min(mid//i, N)
    if n_min >= k :
        answer = mid
        end = mid - 1
    else :
        start = mid + 1

print(answer)

 

 

후기 및 보완할 점

 

이분탐색을 어떻게 적용해야하는지는 알았는데,k번째 수를 구하는 방법을 찾는 데 오래 걸린 것같다.

 

이것도 스터디 끝나고 나면 집중적으로 풀어봐야겠다.