K번째 수 - 1300

[Gold II] K번째 수 - 1300

문제 링크

분류 1️⃣

이분 탐색(binary_search), 매개 변수 탐색(parametric_search)

문제 설명 2️⃣

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

입력 3️⃣

첫째 줄에 배열의 크기 N이 주어진다. N은 10⁵보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(10⁹, N²)보다 작거나 같은 자연수이다.

출력 4️⃣

B[k]를 출력한다.

---

풀이 🔓

예시로 n은 3이라고 하면 배열 A는

1	2	3
2	4	6
3	6	9

배열 B는 크기가 9인 아래 형태의 일차원 배열이다.

1

2

2

3

3

4

6

6

9

이때 k는 7이라고 하면

						❗
1	2	2	3	3	4	6	6	9

6을 가리키게 된다.

일단 배열은 크기 N이 10^5 이므로 N^2인 시간복잡도 알고리즘은 사용할 수 없고, 배열 A를 직접 만드는 것은 메모리 초과이다.(배열 크기 : N^10) 이분탐색을 사용하는데 배열 A를 직접 만들지 않는다.

규칙을 찾아보자면 임의의 수 mid보다 작거나 같은 수의 개수를 구하는 식을 찾을 수 있다.

배열 A의 각 행은 구구단의 1단, 2단, 3단 식이기 때문에 (mid/행번호)는 그 행에서 구하고자 하는 개수(나중에 이 개수들을 다 더하여 배열 B의 k번째 인덱스에 도달할 수 있는지 판단)

단, (mid/행번호)가 N보다 클 경우에는 개수는 N이다
예시) 임의의 수 mid를 4라고 했을 때, 1행은 4/1 = 4 이지만 N = 3보다 크므로 3개이며 4/2 = 2 2행은 2개, 4/3 = 1 로 3행은 1개이다

코드 📃

# 1, 2, 3
# 2, 4, 6
# 3, 6, 9

# 1, 2, 2, 3, 3, 4, 6, 6, 9

n = int(input())
k = int(input())

left = 1
right = k # B[k]가 k보다 큰 수는 나올 수가 없음

while left <= right :
  mid = (left+right)//2

  count = 0
  for i in range(1, n+1):
    count += min(mid//i, n)
  
  if count < k:
    left = mid + 1
  else:
    right = mid - 1

print(left)

의문 (?)

근데 만약 k가 8이면 즉, 8번 째수가 7, 8이 아니고 6임을 어떻게 알 지??

• 1 이하의 수는 1개
• 2 이하의 수는 3개
• 3 이하의 수는 5개
• 4 이하의 수는 6개
• 6 이하의 수는 8개
• 7 이하의 수는 8개
• 8 이하의 수는 8개
• 9 이하의 수는 9개

6을 보면, 6 이하의 수는 8개 이지만, 4 이하의 수는 6이다. 또 7을 보면, 7이하의 수는 8개이지만, 6이하의 수 역시 8개다. 이 말은 7은 존재하지 않기때문이다 (만약 7이 존재하면 7이하의수에서 7은 포함이 되어 갯수를 더 했을 거니깐) 8을 봐도 8이하의 수는 8개이지만, 7이하의 수 역시 8개 따라서 8도 존재 x 그래서 보통 이분탐색의 마지막에는 mid를 출력하지만 left를 출력한 것도 같은 원리였다!!