문제 출처 : https://www.acmicpc.net/problem/1300

---

문제 파악

N = 3이라고 가정하면,
A는 N×N 크기의 배열이고,
원소는 다음과 같이 정의된다.

• 인덱스는 1부터 시작
• A[i][j] = i × j

즉, N = 3일 때,

• 1행: 1×1, 1×2, 1×3 → 1 2 3
• 2행: 2×1, 2×2, 2×3 → 2 4 6
• 3행: 3×1, 3×2, 3×3 → 3 6 9

그래서 전체 표는 이렇게 된다.

	 1  2  3
1	 1  2  3
2	 2  4  6
3	 3  6  9

이를 1차원 배열 B에 차례대로 넣으면

• B = [1, 2, 3, 2, 4, 6, 3, 6, 9]

오름차순 정렬하면

• B = [1, 2, 2, 3, 3, 4, 6, 6, 9]

여기서 k번째 수 (1-indexed)를 찾는 문제다.
예를 들어 k = 7이면 B[7] = 6.

N의 최댓값은 100,000이기 때문에

• 배열 A 크기 = N×N = 10^10 (100억 칸)

그래서 “직접 배열을 만들지 않고도 k번째 수를 찾는 방법”이 필요하다.

---

핵심 아이디어

정렬된 배열에서 k번째 수를 찾는 전형적인 패턴이 있다.

1. 어떤 값 x 를 하나 가정한다.
2. 배열에서 x 이하인 값이 몇 개인지 개수(cnt)를 센다.
3. cnt 와 k 를 비교해서 x 가 k번째 값보다 큰지, 작은지를 판단한다.

이 논리는 되게 단순하다.

• 만약 x 이하가 5개인데, 우리가 찾는 k가 7이라면
  → 7번째 값은 x 보다 커야 한다. (아직 7개를 못 채움)
• 만약 x 이하가 10개인데, k가 7이라면
  → 7번째 값은 x 이하에 있다. (이미 7개 이상 채움)

그래서

• cnt < k → x가 너무 작다 → 더 큰 값 범위로 이동
• cnt ≥ k → x가 충분히 크다 → 더 작은 값 범위로 줄이기

---

조금 더 직관적으로 비유를 해보겠다.

정렬된 키 목록이 있다고 해 보자.

[160, 162, 165, 165, 170, 172, 175, 180, 183, …]

여기서 “7번째로 작은 키”를 찾고 싶다.

1. x = 170 이라고 가정하고, 170 이하가 몇 명인지 센다.

   • 160, 162, 165, 165, 170 → 5명
   • 5 < 7 → 7번째는 170보다 크다.

2. x = 180 이라고 가정하고, 180 이하가 몇 명인지 센다.

   • 160, 162, 165, 165, 170, 172, 175, 180 → 8명
   • 8 ≥ 7 → 7번째는 180 이하에 있다.

이렇게 “x 이하의 개수”만 알면,
x가 k번째 값보다 큰지, 작은지를 알 수 있고
그걸 가지고 x를 이분 탐색으로 조여 나가면
결국 k번째 값에 딱 수렴하게 된다.

---

이제 마지막 퍼즐 조각.
“mid 이하의 원소 개수”를 어떻게 빠르게 셀까?

행 i를 고정하면 A[i][j] 는

i, 2i, 3i, …, Ni

이렇게 생겼다.
여기서 mid 이하가 되는 j 범위를 보자.

i × j ≤ mid
→ j ≤ mid // i

즉, 행 i에서 mid 이하인 원소의 개수는
최대 mid // i 개.

하지만 j 는 1 이상 N 이하이므로
실제 개수는

• mid // i 가 N 보다 크면, 어차피 N개까지만 있음
• mid // i 가 N 이하라면 그 수만큼만 존재

그래서

행 i에서 mid 이하 원소 개수 = min(N, mid // i)

이걸 i = 1부터 N까지 전부 합치면 된다.

cnt = Σ min(N, mid // i) (i = 1..N)

이 cnt 가 바로
“배열 B 에서 mid 이하인 값들의 개수”가 된다.

그래서 코드에서

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

이렇게 된다.

해답 및 풀이

import sys
input = sys.stdin.readline

N = int(input()
k = int(input()

left = 1
right = k  

answer = 0

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

    # mid 이하의 원소 개수 세기
    cnt = 0
    for i in range(1, N + 1):
        cnt += min(N, mid // i)

    if cnt < k:
        # mid 이하 원소가 k개보다 적음 → mid를 키워야 한다
        left = mid + 1
    else:
        # mid 이하 원소가 k개 이상 → mid가 충분히 크다 (줄여볼 수 있음)
        answer = mid
        right = mid - 1

print(answer)

---