[백준] 1300 K번째 수 (파이썬)

골드 Ⅰ

https://www.acmicpc.net/problem/1300

1300번: K번째 수

 

📄 문제

• 세준이는 크기가 N×N인 배열 A를 만들었다.
• 배열에 들어있는 수 A[i][j] = i×j이다.
• 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N 이 된다.
• 배열 A와 B의 인덱스는 1부터 시작한다.

 

B를 오름차순 정렬했을 때, B[k]를 구해보자.

 

---

💡 아이디어

• k보다 작은 숫자가 몇 개인지 찾아내면 k가 몇 번째 숫자인지 알 수 있다.
• 즉, k보다 작거나 같은 원소의 개수가 최소 K개라는 의미이다.
• N은 100,000보다 작거나 같은 자연수이고 제한시간은 2초 이므로 for문을 활용하면 시간초과가 발생한다.
  •  for문을 두 개를 활용하여 리스트를 만든다. (시간복잡도 O(n^2) - 100억)
  • 해당 배열을 오름차순 정렬한다. (시간복잡도 O(nlogn))
  • 해당 값을 찾는다.
  • 대략 시간복잡도는 O(n^3 logn) =  100,000 * 100,000 * 100,000 * 5

• 따라서, 이분 탐색을 활용하여 문제를 해결해야 한다.
• 이분 탐색을 통해 k보다 작은 수가 몇 개인지 찾아낸다.

---

✅ 이분 탐색 활용

1. 최소 값과 최대 값을 범위로 설정해 준다.
   • 인덱스가 1부터 시작하므로 최소 값(start)은 1이다.
   • 전체 범위의 최대 값(end)은 n^2이지만,
   • k번째 수는 k보다 클 수 없기 때문에 최대 값(end)을 k로 지정해도 된다.
2. start와 end의 중간 값인 mid를 설정한다.
3. 해당 숫자(mid) 보다 작거나 같은 숫자를 모두 찾아, 개수를 세어 mid가 몇 번째에 위치한 숫자인지 알아낸다.
   • N×N인 2차원 배열의 각 칸들의 값은 A[i][j] = i×j 형태이므로, 규칙이 존재한다.
   • 각 행은 구구단의 형식을 보이기 때문에 임의의 수 X보다 작거나 같은 수의 개수를 구하는 식이 존재한다.
   • X / 행 번호는 해당 행에서  X보다 작거나 같은 숫자의 개수가 된다.
   • 단, X / 행 번호가 N보다 큰 경우가 존재하므로 최댓값은 N으로 설정해 준다.
4. mid보다 작은 값들의 개수를 구해 cnt에 저장한다.
5. cnt의 개수가 k와 같거나 k보다 크면, 찾는 값(ans)을 갱신해 주고 end의 값을 mid - 1로 변경해 준다.
6. cnt의 개수가 k보다 작으면, start의 값을 mid + 1로 변경해 준다.
7. 최소 mid 값을 찾기 위해 탐색을 반복한다.

 

---

임의의 수 X보다 작거나 같은 수의 개수를 구하는 예시

x / n 은 n 단 (구구단)에서 x보다 작거나 같은 수의 개수이다.

구구단을 예로 살펴보자.

 

1단	1	2	3	4	5	6	7	8	9
2단	2	4	6	8	10	12	14	16	18
3단	3	6	9	12	15	18	21	24	27
4단	4	8	12	16	20	24	28	32	36
5단	5	10	15	20	25	30	35	40	45
6단	6	12	18	24	30	36	42	48	54
...	...	...	...	...	...	...	...	...	...

 

구구단에서 각 단별로 9보다 작거나 같은 수의 개수를 구하면,

• 1단 : 9/1 = 9개
• 2단 : 9/2 = 4개
• 3단 : 9/3 = 3개

 

따라서, 개수를 구하고자 하는 수(x) / 각 단(n)의 몫은 각 단에서 나올 수 있는 x보다 작거나 같은 수의 개수이다.

 

Q) 6 x 6인 2차원 배열에서 10번째 수 구하기.

• 임의의 수 X = 10

 

인덱스	1	2	3	4	5	6	10보다 작거나 같은 수의 개수	누적 개수
1	1	2	3	4	5	6	min(10/1, 6) = 6개	6
2	2	4	6	8	10	12	min(10/2, 6) = 5개	11
3	3	6	9	12	15	18	min(10/3, 6) = 3개	14
4	4	8	12	16	20	24	min(10/4, 6) = 2개	16
5	5	10	15	20	25	30	min(10/5, 6) = 2개	18
6	6	12	18	24	30	36	min(10/6, 6) = 1개	19

• 2차원 배열을 정렬하면,

 

1 번째	2 번째	3	4	5	6	7	8	9	10 번째
1	2	2	3	3	4	4	4	5	5
11 번째	12	13	14	15	16	17	18	19 번째	...
6	6	6	6	8	8	9	10	10

• X = 10 보다 작거나, 같은 수는 총 19개가 존재한다.
• X = 10 은 19번째 수가 되므로 10보다 작은 수를 설정하여 다시 찾아야 한다.
• 따라서, 아래 식을 통해 임의의 수 X가 몇 번째 수인지 찾을 수 있다.

cnt = 0
# N x N 배열에서
# 임의의 수 X보다 작거나 같은 수의 개수를 찾는다. (한 행의 최대 개수는 N)
for i in range(1, N+1):
        cnt += min(X//i, N)

 

📝 문제 풀이 (Code)

import sys
input = sys.stdin.readline

def binary_search(start, end):

    # K보다 작은 숫자가 몇 개인지 찾아내면 K가 몇 번째 숫자인지 알 수 있다.
    while start <= end:
        # 몇 번째 인지 찾을 수
        mid = (start + end) // 2
        # 개수를 저장
        cnt = 0

        for i in range(1, n + 1):
            # mid(확인하는 숫자)를 행으로 나눈 몫은 그 행에서 몇 개의 숫자가 mid보다 작거나 같은지 알 수 있다.
            # n보다 큰 경우가 존재 하기 때문에 최대 n을 갖도록 해준다.
            cnt += min(mid // i, n)

        if cnt >= k:
            ans = mid
            end = mid - 1
        else:
            start = mid + 1

    return ans


n = int(input())
k = int(input())
# 최대 범위는 n^2이다.
# start, end = 1, n*n
# 하지만 k번째 수는 k보다 클 수 없다.
start, end = 1, k
print(binary_search(start, end))