[백준1300번] K번째 수 / Python3

문제

세준이는 N*N크기의 배열을 만들었다. (배열의 방 번호는 1부터 시작한다.)

그 배열을 A라고 했을 때, 배열에 들어가는 수는 A[i][j] = i*j 이다.

세준이는 이 수를 일차원 배열 B에 넣으려고 한다. 그렇게 되면, B의 크기는 N*N이 될 것이다. 그러고 난 후에, B를 오름차순 정렬해서 k번째 원소를 구하려고 한다.

N이 주어졌을 때, k번째 원소를 구하는 프로그램을 작성하시오.

입력

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

출력

k번째 원소를 출력한다.

예제 입력 1

3
7

예제 출력 1

6

나의 풀이

이분 탐색 문제라고 해서 이차원 배열을 그려놓고 한참 생각했다.. 우선 nn의 행렬이 주어지고 각 배열의 원소는 i * j이다. 그럼 모든 원소들 중 최솟값과 최댓값은 1, nn 이 된다.

이차원 배열의 행을 보면 1,2,3,4 ... 증가한다. 그리고 각 행에서 열이 증가할때마다 행번호의 배수들이 나열이 된다. 이 것을 생각하면서 특정 수 보다 작은 수들의 개수를 구하는 방법에 대해 생각해보자.

예를들어 10 * 10행렬에서 15보다 작은 수의 개수를 구해보자. 행은 1,2,3,4로 있을 것이다. 열도 마찬가지로 1부터 4까지 일 것이다. 그럼 1행에서 15보다 작은 수의 개수는 1 x 1, 1 x 2, 1 x 3, ... , 1 x 10 총 10개이다. 2행은 2 x 1, 2 x 2, 2 x 3, 2 x 4, 2 x 5, 2 x 6, 2 x 7로 7개 즉, 15 // 2 == 14와 같다. 이어 3행도 계산해보면 15 // 3 == 5로 5개 ... 이렇게 10까지 구해주어 모든 개수를 더해주면 10 * 10행렬에서 15보다 작은 모든 수들의 개수를 구할 수 있게 된다. 그런데 1행에서의 개수는 왜 15 // 1 == 15인데 왜 10개일까 이건 열의 개수가 10이기 때문이다. 따라서 min()을 사용해서 나눈 값과 열의 수 중에서 작은 값을 넣어주면 된다.

그럼 이제 최솟값과 최댓값을 각각 start와 end값으로 주고 이분 탐색을 진행하면서 각 미드값보다 작은 수들의 개수를 구하여 주어지는 k와 비교를 해가면 문제를 풀 수 있다.

코드

# 1300번 K번째 수

# 이분 탐색
def binSearch(start, end, n, 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:
            answer = mid
            end = mid - 1
        else:
            start = mid + 1
    return answer

# main
n = int(input())
k = int(input())

print(binSearch(1, n*n, n, k))