백준 1300번 - K번째 수

놀랍게도 이분 탐색으로 풀리는 문제이다. B[k]는 어찌됐건 1부터 N²까지 수 중에 하나이기 때문에, 1을 left, N²을 right로 설정하여 이분 탐색을 진행하면 될 것이다.

 

k가 의미하는 것이 무엇일까? N = 5이고, k = 16인 경우를 생각해보자.

N = 5인 경우를 쭉 나열해보면, B[k] = B[16] = 10이다. 10과 N과 k의 관계에 대해 알아내면 대충 감이 올 것 같다.

 

B = [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 8, 8, 9, 10(k), 10, 12, 12, 15, 15, 16, 20, 20, 25] 

 

k번째 이전의 숫자들은 2차원 배열일 때

[1][1] ~ [1][5] : 5개

[2][1] ~ [2][5] : 5개

[3][1] ~ [3][3] : 3개 ([3][4]는 10보다 크기때문에 B[k]보다 작은 값에는 해당되지 않는다.)

[4][1] ~ [4][2] : 2개

[5][1]~[5][2] : 2개

모두 합하면 17개이다. 하지만 꼭 이 개수들의 합이 k와 같다고는 할 수 없다. 왜냐하면 k[17] 또한 10이기 때문이다. 즉 수가 중복이 되기 때문에, k와 같아졌다고 반복문을 탈출하면 안되고 계속 탐색해줘야한다.

 

 

##함수 선언 부분

##변수 선언 부분
ans = 0

##메인 함수 부분
if __name__ == "__main__":
    N = int(input())
    k = int(input())
    left = 1
    right = N ** 2
    while left <= right:
        mid = (left + right) // 2
        cnt = 0
        for i in range(1, N+1): #1,1부터 N,N까지 조건에 맞는 것을 세준다
            if mid // i > N: #찾으려는 수를 i로 나누어주면 개수가 나온다.
                cnt += N #최대 개수가 N이기 때문에 N을 넘으면 N을 더해준다.
            else: #N보다 작으면
                cnt += mid // i #i로 나눈 값을 더한다.
        if cnt >= k:
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    print(ans)

1~N²을 범위로 잡아 이분 탐색을 해야되는 것은 바로 알았지만, 중복되는 수를 어떻게 계산해야할 지를 해결하지 못해서 시간이 꽤 걸렸다. 이분 탐색과 전혀 관련이 없어보이는 문제도 이분 탐색으로 풀 수 있다는 사실이 신기했다.