1300_k번째 수

문제는 더보기!

 

K번째 수 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

21586

7789

5690

37.690%

문제

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

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

입력

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

출력

B[k]를 출력한다.

예제 입력 1 복사

3
7

예제 출력 1 복사

6

 

 

문제에 적힌대로 풀면 엄청 비효율적인 방법일 것이다.

 

다르게 생각하면 7번째의 크기를 구한다는 건 해당 숫자보다 작은 i*j의 개수가 7개라는말과도 같다.

 

즉, 예제에서 나온 7을 생각해보면

 

i*j 로 만들수 있는 수가 앞에 6개있고 7번째 수라는 점이다.

 

 

이를 이분탐색을 통해서 찾는다면 우선 찾는 수는 1에서 k사이일 것이다.  찾는수가 7번째라면 7보다 큰 수가 나올수는 없기 때문

 

그안에서 이분탐색을 값을 찾으면 된다.

 

이때 예를 들어 n = 10 이고 검사할 값(mid) 가 20이라고 생각해보자.

 

이러면 20//1 + 20//2 + ... 이런식의 합이 결국 해당 검사하는 값보다 작은 i*j의 개수가 될 것이다.

 

하지만 이때 생각할거리가 있다. n=10이기때문에 만약 20//1 와같이 20개가 카운트될 수 없다. 이 부분만 생각하고 코드를 짜면 될 것 같다.

 

 

n = int(input())
k = int(input())
start,end = 1,k

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

    cnt =0

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

    if cnt >= k:
        result = mid
        end = mid -1
    else:
        start = mid +1

print(result)