[백준/파이썬] 1300 K번째 수 - 이진 탐색

➰ 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]를 출력한다.

 

 

💡 구현 아이디어

---

문제는 간단하게 NXN의 2차원 배열인 A에서 k번째로 큰 수를 찾는 코드를 작성하면 되는 것이다. 이진 탐색 알고리즘을 이용해 효과적으로 처리할 수 있는데, 이렇게 판단한 근거는 다음과 같다.

 

1) 문제에서 구해야 하는 B[k]에서 리스트 B가 오름차순 정렬된 리스트라는 점

2) 이진 탐색 알고리즘을 사용하지 않고 직관적으로 떠오르는 방법은 이중 for문을 사용하는 것인데, 그렇게 하면 연산이 너무 많아질 것

 

k번째로 큰 수를 찾아내는 것이 목표이다. 이진 탐색으로 우리가 구해야 하는 수보다 작은 자연수의 곱(i * j)이 몇 개나 있는지 찾을 것이다. 어떻게 할지 바로 생각나진 않으니 예시를 직접 나열해 보며 규칙을 발견하도록 하겠다.

 

예를 들어 N=10인 배열 A에서 20보다 작거나 같은 수가 몇 개나 있는지 생각해보자.

1*1 ~ 1*10

2*1 ~ 2*10

3*1 ~ 3*6

4*1 ~ 4*5

...

...

9*1 ~ 9*2

10*1 ~ 10*2

이렇게 있을 것이다. 처음엔 잘 안 보일 수도 있지만, 어떻게든 위에 나열해 놓은 결과들에서 규칙을 발견하고자 하면 보일 것이다. 우리가 봐야 하는 것은 개수인데, 각 행에서의 개수는 곧 20을 행의 숫자로 나눈 값과 같다. 단, 각 행의 원소의 개수(N)를 초과할 수 없다.

 

1*1 ~ 1*10  >>  10개  (20//1=20은 10보다 크므로)

2*1 ~ 2*10  >>  20//2=10개

3*1 ~ 3*6    >>  20//3=6개

4*1 ~ 4*5    >>  20//4=5개

...

...

9*1 ~ 9*2      >>  20//9=2개

10*1 ~ 10*2  >>  20//10=2개

 

위 과정을 코드로 작성하면 다음과 같다.

temp = 0

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

 

이렇게 특정 숫자(mid)보다 작거나 같은 숫자들이 몇 개인지 찾아내서 mid가 몇 번째로 큰 숫자인지 알 수 있다.

 

💻 소스 코드

---

N, K = int(input()), int(input())
start, end = 1, K

while start <= end:
    mid = (start + end) // 2

    temp = 0
    for i in range(1, N+1):
        temp += min(mid//i, N) # mid가 몇 번째로 큰 숫자인지 찾아냄

    if temp > K: # 이진 탐색 실행
        end = mid - 1
    elif temp < K:
        start = mid + 1
    else:
        answer = mid

print(answer)