180. 1300(K번째 수) - 파이썬

import sys
input = sys.stdin.readline

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

start = 1
end = K
result = 0

while(end - start >= 0):
    mid = (start + end) // 2
    cnt = 0

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

    if(K <= cnt):
        result = mid
        end = mid - 1
    else:
        start = mid + 1

print(result)

문제요약

2차원 배열 A[i][j] = i * j 를1차원 배열 B로 만들고 정렬했을 때 K번째 즉 ,B[K]를 구하라

설명

이 문제는 배열도, 정렬도 쓰이지 않는다.

신기하게  이분 탐색으로 해결된다.

백준에서도 

이분 탐색으로 풀 수 있는 놀라운 문제로 소개하고 있다.

먼저 간단히 문제에 대해서 설명 하겠다.

백준에서 입출력이 3, 7이다.

따라서 다음과 같이 3*3의 [i][j] = i * j 행렬을 만들 수 있다.

이 행렬을 B[K]에 넣으면,

오름차순으로 정렬한 행렬이 B행렬이 된다.

이 중 7번째 즉 6이 정답이 된다.

하지만 지금 방식은 브루트포스 방식으로 분명히 시간초과가 발생한다.

 

자 그러면 어떻게 해결하냐

 

A행렬은 구구단과 같다.
4단으로 하면

출처: https://st-lab.tistory.com/281

5단으로 하면

다음과 같이 된다. 

 

5 * 5를 가지고 한번 생각해보자.

각 단별로 5보다 작거나 같은 수의 개수를 찾으라 하면 

다음과 같이 총 10개를 찾아낸다.

이 10개는 K가 될것이다!

따라서 B[10] = 5가 정답이 된다.

 

다시말해 B[K]의 의미는 각 단별로 x보다 작거나 같은 수의 개수를 찾으라는 말과 같다.

이게 가능한 이유는 오름차순으로 정렬을 하기 때문이다.

 

만약 N은 5, K는 9로 입력이 들어왔을 경우라 해도 다음과 같은 코드로 인해 결과 5는 바뀌지 않는다.

    if(K <= cnt):
        result = mid
        end = mid - 1
    else:
        start = mid + 1

결과 값을 result에 저장하고 계산은 계속 진행하기 때문이다.

 

자 그럼 이 문제에서 중요했던 이분 탐색 부분을 보자.

start = 1
end = K
result = 0

while(end - start >= 0):
    mid = (start + end) // 2
    cnt = 0

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

시작은 1로 시작한다 (배열의 인덱스는 1부터 시작하기 때문이다.)

끝은 K가 될것이다. (K인덱스보다 큰 건 필요 없다.)

 

반복문 부분을 보면

        cnt += min(mid // i, N)

결국에 x보다 작거나 같은 수의 개수를 구하는 것이다.

 

반복문을 통해 총 개수를 구하고 

    if(K <= cnt):
        result = mid
        end = mid - 1
    else:
        start = mid + 1

총 개수가 K보다 작거나 같다면 result에 mid 값을 넣고 end 부분을 mid - 1 해준다.

반대로 총 개수가 K보다 크다면 start부분을 mid + 1 해주어 while문을 돌려주는 것이다.