[백준] 1300번: K번째 수 (python)

1300번: K번째 수

---

문제 )

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

 

 

 

입력 :

첫째 줄에 배열의 크기 N이 주어진다. N은 10^5보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(10^9, N2)보다 작거나 같은 자연수이다.

 

 

출력 :

B[k]를 출력한다.

 

풀이)

솔직히 혼자 풀었으면 못 풀었을 것 같은 문제이다.

풀이를 알려줘서 망정이지..

 

이 문제의 풀이 전략은 다음과 같다.

 

 

n = 3라고 할 때, 배열  B는 

1 2 2 3 3 4 6 6 9 가 된다. 이 배열을 이용하면,

 

만약 B[7]을 구하라고 한다면,

 

배열 B	1	2	2	3	3	4	6	6	9
인덱스	1	2	3	4	5	6	7	8	9
인덱스보다 작거나 같은 수의 개수	1	3	5	6	6	8	8	8	9
답이 될 수 있는가?	X	X	X	X	X	O	O	O	O

 

가 되므로 이진탐색이 가능해진다.

 

그렇다면 인덱스보다 작거나 같은 수의 개수는 어떻게 알 수 있을까?

 

예를 들어 n = 100, k = 140이라고 하면, 처음이 1로 시작하는 1번째 행에서는 1 ~ 100 (step = 1)까지의 수가 있을테고, 

k보다 작거나 같은 수는 100개가 있다.

2로 시작하는 2번째 행에서는 2 ~ 200 (step =2)이고, k보다 작거나 같은 수는 70개가 나오게 되므로, 

for문을 이용하여 k보다 작거나 같은 수의 개수를 구할 수 있게 된다.

 

이를 코드로 표현하면 다음과 같다. 

 

def check(x):
    total = 0
    # 행렬에서 x보다 작거나 같은 수의 개수.
    for i in range(1, n + 1):
        # x보다 i가 크면 곤란하므로, min을 이용해
        # 많아도 n개를 넘기지 않도록 한다.
        total += min(n, x // i)
 
    # 만약 x보다 작거나 같은 수의 개수가 k보다 크거나
    # 같아야 정답이 될 수 있다.
    return total >= k
 
 
n = int(input())
k = int(input())
 
s = 1
e = n * n
 
while s <= e:
    mid = (s + e) // 2
 
    # 정답이 될 수 있으면, 그중 가장 작은것을
    # 정답으로 뽑는다.
    if check(mid):
        ans = mid
        e = mid - 1
    else:
        s = mid + 1
 
print(ans)

---

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

1300번: K번째 수