[백준(BOJ)] #1300- K번째 수 (파이썬, PyPy3)

문제

 

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

1300번: K번째 수

 

---

문제 풀이

배열의 크기 N이 10^5보다 작거나 같은 자연수이기 때문에 일차원 배열로 변환하고 정렬해서 구하기는 불가능합니다. 이분 탐색을 사용하여 이 문제를 해결할 수 있습니다.

 

2022.08.11 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 이분 탐색(Binary Search)

[파이썬으로 배우는 알고리즘] 이분 탐색(Binary Search)

 

배열에 들어가는 숫자가 i * j라는 성질을 이용해서 배열의 모든 숫자를 위와 같이 나타낼 수 있습니다. 

이 배열을 1차원 배열로 변환한 뒤 정렬을 하면

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

가 되고, 7번 째로 오는 숫자가 6이니 정답은 6이 되는 것이죠

 

그렇다면 7번 째 숫자가 6이라는 것을 어떻게 이분탐색을 사용하여 구할 수 있을까요?

 

구하고자 하는 수가 a 일 때 

a 이하인 수의 개수 = 각 행에서 a 이하인 수의 개수는 a를 행번호로 나눈 몫이고, 각 행에서 나온 결과를 더하면 됨(몫이 N보다 크면 N)

예를 들어 위와 같은 배열에서 6 이하인 수의 개수를 구한다고 해보겠습니다.

 

1) 1행

6/1 = 6, 6은 N보다 크므로 1행에 6 이하인 수의 개수는 3개

 

2) 2행

6/2 = 3, 2행에 6 이하인 수의 개수는 3개

 

3) 3행

6/3 = 2, 3행에 6 이하인 수의 개수는 2개

 

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

총 8개

 

구하고자 하는 값을 이분탐색을 사용해 조정하며 위 조건을 만족하는 값으로 구해주면 됩니다.

 

---

구현

코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    k = int(input())

    lt, rt = 0, k

    res = 0

    while lt <= rt:
        mid = (lt + rt) // 2

        cnt = 0
        for i in range(1, n+1):
            cnt += min(mid // i, n)

        if cnt >= k:
            res = mid
            rt = mid - 1
        else:
            lt = mid + 1

    print(res)

 결과