1300 k번째 수

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

N = int(read())
K = int(read())

start = 1
end = K

while start <= end :
    m = (start + end) // 2
    num_cnt = 0

    for n in range(1,N+1):
        num_cnt += min(m//n,N)

    if num_cnt < K :
        # m을 크게하기위해 start를 변경
        start = m + 1
    else :
        end = m - 1
print(start)

3. 생각 및 풀이

생각

아오.. 어렵다 이진탐색은 알고리즘 자체가 잘 이해가 안된다 특히 뭔가 카드가 주어져서 index를 갖고노는 것이 아닌, 숫자 자체를 찾는 과정이 그런 것 같다. 이건 계속 복습을 통해서 해당 개념을 완벽히 숙지해야할 것 같다.

풀이

인터넷에 많은 풀이들이 있는데, 읽어도 읽어도 잘 이해가 되지 않아서 내가 이해한 방식대로 최대한 길게 늘여써보겠다.

k번째 수를 m이라고 해보자. 그럼 m보다 작거나 같은 수들의 개수가 k개가 되야할 것이다.

N X N행렬에서 각 행은 i(i=1,2,…N)의 배수인데, m보다 작은 수들은 다음과 같이 표현할 수 있다. $m>=i\times j$ 부등식을 바꾸게 되면 $j<=\frac{m}{i}$가 된다. 그러나 j=1,2,…N인 자연수이므로 m을 i로 나눴을 때 몫이 j가 된다. 그리고 최대 값은 N이다.

따라서 모든 행에서 m보다 작거나 같은 수들의 개수를 전부 센 후, 우리의 목표인 K개가 되는지 확인하면 된다.

여기서 중요한 점은 분명히 2x3=6 이나 3x2=6처럼 겹쳐있는 수가 있을 것이다. 그럴 때, 우린 이진 탐색의 끝까지 가서 start를 선택하는 것이 옳다는 것이다.

개수가 K개보다 작다면 이는 start의 값이 작아서 m이 작게 측정됬기 때문에 start를 키워야한다.

개수가 K개보다 크거나 같다면 start값을 끌어 올릴때까지 end 값을 고쳐주는 느낌이다.

지금 이 글을쓰는 순간에도 잘 이해가 안가는 부분이 있다.. 복습하면서 깔끔하게 정리가 되면 다시 정리해보자.