[백준 #1300번 / Python] K번째 수

. 문제)

https://www.acmicpc.net/problem/1300
세준이는 크기가 NxN인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j]=ixj 이다.
이 수를 일차원 배열 B에 넣으면 B의 크기는 NxN이 된다.
B를 오름차순 정렬했을 때, B[k]를 구해보자. (배열 A와 B의 인덱스는 1부터 시작한다.)

. 접근)

가장 직관적인 방법은 단순히 B를 정렬 후, B[k]를 반환하는 것이라 볼 수 있다.
그러나 이 경우 quick sort를 기반으로 하는 파이썬의 라이브러리 sort 함수를 사용해도 O(NlogN)이기에 시간초과가 발생한다.
따라서 이 문제는 정렬 알고리즘을 사용하는 게 아닌, 이중탐색(Binary Search) 알고리즘의 사용이 핵심이다.
그렇다면 이중탐색의 탐색할 구간은 어떻게 정해야 할까? 아래 그림을 보자.

아래 예는 N=5일 때를 나타낸 그림이다.

2차원 배열 A의 원소들을 각 행별로 분석을 해보면, 인덱스 i에 1부터 N까지 곱한 값이 나열되어 있음을 볼 수 있다.
이후 변수 S보다 작거나 같은 원소들의 개수를 센다면 B를 정렬하지 않고도 정렬한 것과 같은 결과를 낼 수 있다.
아래는 i행에 대해, S보다 작거나 같은 원소의 총 개수 count를 계산하는 방법을 나타낸 그림이다.
단순히 S//i 라고 생각할 수 있지만, 그렇게 되면 위의 그림에서 1행의 count는 7이 되기에 min 함수를 사용해야 한다.

. 풀이)

• start=0, end=k+1 로 두 개의 매개변수를 잡는다. (B[k]는 무조건 k보다 작으므로)
• 1행부터 i행까지 total변수에 각 행의 count들을 더한다.
• 만약 total 값이 k보다 크거나 같다면, S보다 작은 수들이 많았다는 뜻이므로 end=mid-1 로 변경해 mid 값을 줄인다. 또한 정답 변수 res에 mid 값을 갱신한다.
• 만약 total 값이 k보다 작다면, 마찬가지로 start=mid+1 로 변경한다.
• 이중 탐색이 끝난 뒤 res 값을 리턴한다.

. 코드)

import sys
input=sys.stdin.readline

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

def binary_search(start,end):
    res=0
    while start<=end:
        mid=(start+end)//2
        total=0
        for i in range(1,n+1):
            total+=min(mid//i,n)
        if total>=k:
            end=mid-1
            res=mid
        elif total<k:
            start=mid+1
    return res
print(binary_search(start,end))

. 주의할 점)

이 문제에서 헷갈릴 만한 부분은 if 문에서 등호를 total<=k 로 붙여도 되는 게 아닌가?라는 생각이다.
하지만 조금만 생각해 보자. start=0, end=k+1 이고 이중 탐색 변수 mid는 이 둘 값의 중간값이므로 배열 A안에 없는 값이 나올 수도 있다.
이 말은 곧 실제 배열 안에 없는 수가 정답으로 도출될 수 있다는 것이다.

예를 들어보자. S가 정답, S+1이 배열 안에 없는 수라 가정하자.
만약 S+1이 먼저 계산되고 if total<=k 문 안에 들어갔다면, start=mid+1이 되고 res=S+1 로 갱신될 것이다.
그렇게 되면 다음 mid 값이 상대적으로 증가하여 오답을 도출하게 된다. (mid 값이 S와 점점 멀어짐)

그러나 본 코드와 같이 if total>=k 로 등호 부분을 처리해 주면, end=mid-1이 되고 mid 값이 상대적으로 감소한다.
따라서 S+1로 잘못 계산했더라도 이중 탐색을 계속 진행하여 결국 정답을 얻어낼 수 있다.