백준 / 1300번: K번째 수 / python

1300번: K번째 수

자세한 해설

단순하게 N*N 배열을 정의 한 후 B를 만들어서 정렬을 하면 시간초과가 나오기도 전에 메모리초과가 나옵니다.

이 문제를 풀기 위해서는 이진탐색을 활용해야 합니다.

 

이진탐색으로 B[k]를 찾는 과정을 크게보면 다음과 같습니다.

 

1. 이진탐색으로 mid를 구합니다.
2. mid가 B에서 몇번째 숫자인지 구합니다.
3. 만약 mid가 k번째 수라면 index도 k라는 뜻이고, mid = B[k] 가 됩니다.

"mid가 B에서 몇번째 숫자인지"는 A의 각 행에서 "mid이하의 수"를 세면 됩니다.

다음은 N=3, k=7 의 예제입니다.

 

1	2	3	구구단 1단
2	4	6	구구단 2단
3	6	9	구구단 3단

 

i행이 구구단 i단의 형태이므로 mid // i 를 하면 i행의 "mid이하의 수"를 셀 수 있습니다.

1단부터 N단까지 "mid이하의 수"를 전부 세면 mid의 index가 됩니다.

이때 각 행에서 mid이하의 수 개수의 최대값은 N이므로 주의해서 구현합니다.

    mid = (left+right)//2
    index = 0
    for i in range(1,N+1):
        index += min(mid//i, N)

 

이제 mid의 index와 k를 비교합니다.

 

• index가 k 이상이면 mid를 저장합니다. 그리고 더 낮은 mid를 탐색합니다.
• index가 k 미만이면 더 높은 mid를 탐색합니다.

    if index >= k:
        answer = mid
        right = mid - 1
    else:
        left = mid + 1

여기서 주의할점이 중간에 만족하는 mid와 index를 찾더라도 left가 right를 넘어갈 때 까지 계속 반복합니다.

만족하는 mid중 가능한 최소값을 찾기 위함입니다. 왜일까요?

 

다음은 예제에서 B[k]값과 k값 입니다.

B[k]	k
1	1
2	3
3	5
4	6
5	6
6	8
7	8
8	8
9	9

B[k]=6 이여도 k=8

B[k]=7 이여도 k=8

B[k]=8 이여도 k=8 입니다.

 

하지만 예제의 행렬을 보면 7이나 8이라는 B[k]는 있을 수 없습니다. 오직 최솟값인 6만이 B[k]로 존재합니다. 또한 k의 값도 7이 아닌 전부 8입니다. 중복되는 숫자가 많고 없는 숫자도 존재하기 때문입니다.

많은 부분에서 이런 현상이 일어나기 때문에 찾고자 하는 k와 index가 정확하게 일치하지 않더라도 만족하는 index의 최소값을 찾아야 합니다.

이 부분이 단순한 이분탐색이 아닌 매개 변수 탐색이 적용되는 이유입니다.

 

전체코드

N = int(input())
k = int(input())
left, right = 0, N*N
while left <= right:
    mid = (left+right)//2 # B[k]
    index = 0 # k
    for i in range(1,N+1):
        index += min(mid//i, N)
    
    if index >= k:
        answer = mid
        right = mid - 1
    else:
        left = mid + 1
    
print(answer)

잡담

코드는 간단하지만 문제를 푸는 방향성과 구현하기 위해 index를 찾는 과정 자체가 생각하기 쉬운 문제는 아니였습니다. 문제풀이를 직접 올리면서 오래 해석해야 이해할 수 있었습니다.

매개 변수 탐색이 적용되는 여러 문제를 푸는대 많은 도움이 되었습니다.