[백준] 1300 K번째 수

문제

세준이는 크기가 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]를 출력한다.

 

 

접근 방법

해결하지 못해 다른 분이 작성하신 접근 방법을 참고하였다.

 

문제를 보고 가장 먼저 N*N 배열을 만들고 오름 차순 정렬하는 것을 생각할 수 있다. 하지만 이러한 방법을 사용할 경우 O(N^2) 시간이 걸리기 때문에 매우 비효율 적이고 메모리도 많이 필요하다.

 

따라서 이분 탐색을 사용하여 시간을 줄여야할 것이다.( 이분 탐색을 사용해야하는 것까지는 알고 있었지만 left, right를 어떻게 설정해야할 지 접근할 수 없었다.)

 

K 번째 수를 구하기 위해서는 B[K]의 어떠한 수 X보다 작은 수가 몇개인지 구할 수 있으면 해결이 가능하다. 따라서 어떤 수 X를 임의로 선택하고 기준으로 설정해야한다.

 

X를 선택하기 위해 left=0, right=K로 한다. 이때 right를 K로 설정한 이유는 직접 수를 오름차순으로 나열해보면 알 수 있듯이 B[K]는 반드시 K보다 작거나 같은 수가 된다.

 

 

다음은 X보다 작은 수의 개수를 구하는 방법이다.

 

10 X 10 배열은 아래와 같이 이루어진다.

 

1*1|1*2|1*3|1*4|1*5|1*6|1*7|1*8|1*9|1*10|2*1|2*2|2*3|2*4|2*5|2*6|2*7|2*8|2*9|2*10|3*1|3*2|3*3|3*4|3*5|3*6|3*7|3*8|3*9|3*10|...각 행에서 20보다 작은 수의 개수를 구하기 위해서는 20을 행의 넘버로 나눈 몫을 구하면 된다. 

 

그리고 주의해야 할 점은 20 // 1 = 20 이지만 N = 10이기 때문에 개수가 N을 넘을 수 없다.

 

소스 코드

import sys
readline = sys.stdin.readline

def main():
    N = int(readline())
    K = int(readline())

    left = 0
    right = K # K번째 수는 항상 K보다 작거나 같다. B[K] <= K
    ans = 0

    while left <= right:
        mid = (left + right) // 2
        
        cnt = 0
        for i in range(1, N+1):
            cnt += min(mid // i, N) 
            # ex) 10*10 배열에서 20보다 작거나 같은 수 구한다 가정
            # 20 // 1 = 20 >> N = 10 이기 때문에 20이 아닌 10개가 맞음
            # 따라서 min(mid//i, N) 
        if cnt >= K:
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    
    print(ans)  
if __name__ == "__main__":
    main()