[1300] k번째 수 (이분탐색, 2차원 배열)

1300번: K번째 수

 

분석

n=3, k=7로 가정

중앙값보다 작거나 같은 수의 개수 = 중앙값을 N으로 나눈 값

 

1. 최초의 중앙값 : 4 = (1+7)/2

1*1 = 1	1*2 = 2	1*3 = 3	1행 : 4/1 = 4지만 행의 크기가 3개이므로 3
2*1 = 2	2*2 = 4	2*3 = 6	2행 : 4/2 = 2
3*1 = 3	3*2 = 6	3*3 = 9	3행 : 4/3 = 1

cnt를 다 더하면 5이므로 k(7)보다 작음 => 중앙값을 증가시킴 (시작 인덱스= 중앙값 +1)

 

2. 중앙값 : 6 = (5+7)/2

1*1 = 1	1*2 = 2	1*3 = 3	1행 : 6/1 = 6지만 행의 크기가 3개이므로3
2*1 = 2	2*2 = 4	2*3 = 6	2행 : 6/2 = 3
3*1 = 3	3*2 = 6	3*3 = 9	3행 : 6/3 = 2

cnt를 다 더하면 8이므로 k(7)보다 큼 => 정답값 저장, 중앙값을 감소시킴 (종료 인덱스= 중앙값 -1)

 

3. 중앙값 : 5 = (5+5)/2

1*1 = 1	1*2 = 2	1*3 = 3	1행 : 5/1 = 5지만 행의 크기가 3개이므로3
2*1 = 2	2*2 = 4	2*3 = 6	2행 : 5/2 = 2
3*1 = 3	3*2 = 6	3*3 = 9	3행 : 6/3 =2

cnt를 다 더하면 6이므로 k(7)보다 작음 => 중앙값을 증가시킴 (시작 인덱스= 중앙값 +1)

 

4. 시작인덱스 : 6, 종료 인덱스 :5 => 종료  

 

풀이

n=int(input())
k=int(input())

start=1
end=k
res=0

# 이진탐색 수행 => k번째 수 체크 : k보다 작은 수가 몇개인지 체크
while start<=end:
    mid=int((start+end)/2) # 중앙 인덱스
    cnt=0 # 중앙값보다 작은 수

    # 중앙값보다 작은 수 계산
    for i in range(1,n+1):
        cnt+=min(int(mid/i), n) # 중앙인덱스를 i(행번호)로 나눈 값: 중앙값보다 작거나 같은 개수
    if cnt<k: # 현재 중앙값보다 작은 수의 개수가 k보다 작음 => k번째 수 아님
        start=mid+1
    else: # 현재 중앙값보다 작은 수의 개수가 k보다 크거나 같음
        res=mid
        end=mid-1
print(res)