[백준] 1300 : k번째

정답코드 (PYTHON)

import sys
input = sys.stdin.readline

N = int(input()) ; k = int(input())
mn, mx = 1, k

while mn <= mx:
    mid = (mn+mx) // 2
    n = 0 # mid값보다 작은 요소 개수
    for i in range(1, N+1):
        n += min(mid//i, N) # i번째 행에서 mid값보다 작은 요소 개수
    if n < k: # k개보다 적으면 더 큰 값 조사
        mn = mid + 1
    else: # k개보다 많거나 같으면 더 작은 값 조사
        mx = mid - 1
print(mn)

아래 코드처럼 행렬의 모든 요소를 arr에 넣고서 정렬한 다음 k번째 수를 찾으면 메모리 초과가 발생한다.

arr = [i*j for i in range(1,N+1) for j in range(1,N+1)]

따라서 다른 방법이 필요하다.

행렬에 어떤 수보다 작거나 같은 요소가 몇 개인지 알아낼 수 있음을 이용해서 이분 탐색을 통해 해결할 수 있다.

10*10 형태의 행렬을 가정해보자.

	1열	2열	..	j열	..	10열
1행	1*1	1*2	..	1*j	..	1*10
2행	2*1	2*2	..	2*j	..	2*10
..	..	.	..	..	..	..
i행	i*1	i*2	..	i*j	..	i*10
..	..	..	..	..	..	..
10행	10*1	10*2	..	10*j	..	10*10

따라서 행에서 20보다 작은 수의 개수는 다음과 같다

	20을 i로 나눈 값	i번째 행에서 20보다 작은 수의 개수
1번째 행	20//1 = 20	10개
2번째 행	20//2 = 10	10개
3번째 행	20//3 = 6	6개
..	..	..
i번째 행	20// i	min(20//i,N)

이를 이용해 mid값을 지정하고, mid가 몇 번째 값인지 확인하는 과정을 반복하여 k번째 값을 구한다.