[Baekjoon, Python] 1300번 : K번째 수

도입

백준 단계별 풀기에서 이분탐색, 여섯 번째 문제이다.

백준 1300번 문제, 입력, 출력

---

백준 1300번 입출력 예제 1

---

풀이

0. 쉽게 이중for문으로 직접 값을 넣어서 NxN집합을 구성하는 것을 생각할 수 있으나, 절대 이렇게 접근하지 말자. 단계별 문제에서 이분탐색으로 분류되어서 이분탐색으로 접근을 시작했지, 이런 힌트가 없었다면, 엄청 돌아갔을 것 같다. 

 

1. 이분탐색의 첫 번째 요점은, 'mid값을 무엇으로 설정할 것인가'이다. 이말인 즉슨, low와 high값을 뭘로 선택할 것이냐 이다. 여기서 놀라운 점은 입력받는 k값을 high값으로 설정한다는 것이다. 그리고 mid값을 B[k]값으로 반환한다는 점이다. 왜? 

 

2. 일단, NxN의 집합을 1차원 배열에 오름차순 정렬을 하게되면, 그리고 인덱스가 1부터라면, 각 인덱스에 해당하는 값들은 인덱스보다 작거나 같은 값을 가진다. (index >= value) 동의하는가?

 

- 3x3

index	1	2	3	4	5	6	7	8	9
value	1	2	2	3	3	4	6	6	9

- 4x4

index	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
value	1	2	2	3	3	4	4	4	6	6	8	8	9	12	12	16

- 5x5

index	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
value	1	2	2	3	3	4	4	4	5	5	6	6	8	8	9	10	10	12	12	15	15	16	20	20	25

증명은 다른 블로그에도 많이 있으니, 참고하면 될 듯하다. 우리는 경험으로 알 수 있다. 예제에서는 3x3에서 index 7에 해당하는 값을 물었고, 6이 정답이다. 그렇다면 어떻게 k를 high에 두고 mid 값으로 index를 계산하는 것일까?

 

3. 집합을 그려보면 알겠지만, 대각선으로 대칭임을 알 수 있다. row by row로 생각해보자. row by row라는 것은 for문을 돌릴 때 row를 x값으로 잡고 +1씩 하겠다는 것이다. count의 초기값은 0이라고 하겠다.

	mid(1+k//2)	x (row를 담는 변수)	mid // x	min ( mid // x, N )	count += min ( mid // x, N)
row 1	4	1	4	3	3
row 2	4	2	2	2	5
row 3	4	3	1	1	6

이렇게 계산한 count값을 k와 비교한다. 그 다음은 코드를 참고하면 되겠다.

---

코드

from sys import stdin

var_N = int(stdin.readline())
var_k = int(stdin.readline())

def count_value(mid, N):       #해당 mid값의 번째를 count하는 함수
    temp_count = 0

    for x in range(1, N+1):                # key algorithm
       temp_count += min(N, mid//x)
    
    return temp_count

def binary_k(var_N, var_k):
    high, low = var_k, 1

    while low <= high:
        mid = (high + low)//2

        count = count_value(mid, var_N)

        if count < var_k:
            low = mid + 1
        elif count >= var_k:
            rtn = mid
            high = mid - 1 

    return rtn

print(binary_k(var_N,var_k))

---

마무리

처음 문제를 봤을 때, 이게 어떻게 이분탐색으로 접근할 수 있지? 라는 생각을 했다. 만약에 단계별 풀기 이분탐색란에 없었다면, 이분탐색의 접근을 떠올리지도 못 했을 것이다. 기억해두자.