[Python 3] BOJ - 1300 "K번째 수"

 # 문제 링크

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

1300번: K번째 수

 

 # 풀이

 개인적으로 이 문제는 이분 탐색이 핵심이라고 생각한다. 만일 어떤 수 X보다 작거나 같은 수가 K개 이상이라고 한다면, 그 때 X는 K번째 수의 후보임에는 자명하고 반대 경우, 즉 X 이하의 수가 K개 미만이면 그 때 X는 K번째 후보가 될 수 없다는 것이 자명하다. 따라서, 어떤 수 X 이하의 수가 K 이상인 X 중 가장 작은 수가 정답이 됨을 알 수 있다

 그런데 이분 탐색에 있어 현재 수 X보다 작은 수의 갯수를 어떻게 구할 수 있을까? 간단하다. 전체 N X N 행렬이므로 각 i번째 행의 수들은 i, 2i, 3i, ...로서 i의 배수가 됨을 알 수 있다. 따라서, X를 i로 나눈 몫이 된다. i행일 때 X보다 작거나 같은 수가 P개라고 하자. 따라서 i, 2i, 3i, ...Pi까지는 X보다 작거나 같음을 알 수 있다. 그런데 (P+1)i는 X보다 크기 때문에 X를 i로 나타낸다면, X = Pi + "어떤 수"가 될 것이다. 이 때, 어떤 수는 반드시 0이상 i미만의 수이므로 X는 i의 몫과 나머지꼴로 표현이 가능하다. 따라서, X를 i로 나눈 몫이 i행을 기준으로 X이하의 갯수를 구하는 것과 같다

 따라서, 모든 행에 대하여 X를 나눠주되, 배열의 크기를 벗어날 수는 없으므로 n보다 크다면 n으로 갯수를 제한해준다. 이렇게 임의의 X에 대하여 X 이하의 수를 구하여 K 미만이라면 X보다 더 작은 수는 역시나 K미만일 것이므로 X보다 큰 수를, 반대의 경우는 그런 수 중에서 최소값을 구해야 하기 때문에 X보다 작은 수를 다음 탐색에 고려해야 한다

 

 # 코드

import sys, math

# check : 임의의 수 num보다 작거나 같은 갯수가 K 이상인지 리턴하는 함수
def check(num):
    cnt = 0
    for i in range(n):
        cnt += min(num // (i + 1), n)
    return cnt >= k

# 입력부
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())

# 이분 탐색
left = 0
right = 9876543210
ans = []
while left <= right:
    mid = (left + right) // 2
    # 조건에 맞지 않는 경우 수가 너무 작으므로 left를 증가
    if not check(mid):
        left = mid + 1
    # 조건에 맞는 수이기 때문에 현재 수보다 크면 역시 조건에 맞기 때문에 right를 감소
    else:
        ans.append(mid)
        right = mid - 1
        
# 정렬되어 있다고 문제에서 제시했기 때문에 최소값 출력
print(min(ans))