백준, K번째 수, 1300, 파이썬

[유형]

이분탐색

 

[문제링크]

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

 

[요약]

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

 

[문제풀이]

N=3, 7보다 작거나 같은 수를 생각해보면

1행의 경우, 1*1~1*3까지 3개,

2행의 경우, 2*1~2*2까지 2개,

3행의 경우, 3*1~3*2까지 2개이다.

 

temp에 저장된 값이 K개보다 많거나 같으면, mid 값을 줄이고

K보다 적으면 mid 값을 늘린다.

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()

N = int(input())
K = int(input())

start,end = 1, K

while start <= end:
    mid = (start + end) // 2
    temp = 0

    for i in range(1,N+1):
        temp += min(mid//i,N)
    if temp >= K:
        end = mid-1

    else:
        start = mid+1
print(start)