백준 1300번: K번째 수 (Python)

접근

문제 설명에 '의외로 이분 탐색으로 풀 수 있는 놀라운 문제'라고 했는데 정말 신기하게 이분 탐색으로 풀 수 있었다. 이분 탐색 알고리즘으로 풀기 위해 고민을 좀 많이 하였다.

매 탐색 과정에서 cnt를 계산해 주는데, 이 cnt는 N * N 행렬의 각 행에서 mid 값보다 작은 수들의 개수를 의미한다. 물론 모든 행렬을 순환하면서 mid 값과 비교하지는 않고, min(n, mid // i) 수식을 이용하여 계산해주게 된다. 예를 들어 n이 3인 행렬에서 mid가 4일 경우, n값 3과 mid // i = 4 중 작은 값은 3이다. [1, 2, 3] 중 4보다 작은 값은 세개 모두 해당한다는 의미이다. 이런 식으로 계산하여 mid 값보다 작은 수들의 개수를 모두 구한 cnt와 target을 비교한다.

mid 값보다 작은 수의 개수(cnt)가 target보다 클 경우, target에 도달하기 위해서는 mid값보다 작은 값으로 계산해야 하므로 start부터 mid - 1 까지 범위로 이진탐색을 계속한다.

코드

import sys

n = int(sys.stdin.readline())
target = int(sys.stdin.readline())
cnt = 0


def binarysearch(start, end, target):
    global cnt
    if start > end:
        return start
    mid = (start + end) // 2
    cnt = 0
    for i in range(1, n + 1):
        cnt += min(n, mid // i)
    if cnt < target:
        return binarysearch(mid + 1, end, target)
    else:
        return binarysearch(start, mid - 1, target)


print(binarysearch(1, target, target))

더 생각해 볼 것?

머리로는 이해하였으나 이를 말로 설명하는 것은 굉장히 어렵다고 특히 이번 문제를 설명하면서 느꼈다. 접근 방법에 대해 다시한번 정리해보는 시간을 갖도록 해야겠다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!