PS Featured

[PS] BOJ 1300 / K번째 수

Minjun Kim

13 Jan 2026 • 3 min read

Thumbnail: Photo from Eduardo Soares (Unsplash)

문제 링크: https://www.acmicpc.net/problem/1300

풀이

N x N 크기의 2차원 배열의 $i$번째 행, $j$ 번째 열의 원소는 $i \times j$입니다.
이 2차원 배열을 1차원 배열로 펼치고 정렬한 뒤, 오름차순으로 $K$번째 수를 찾는 문제입니다.

정렬된 배열에서의 $K$번째 수라는 것은, 이 수와 같거나 작은 수가 $K$개 미만인 수를 의미합니다. 따라서, "어떤 수 $M$에 대해 $M$보다 작거나 같은 수가 $K$개 미만인가?" 라는 결정 문제를 통해 매개변수 탐색을 진행하면 YYYY...YNNNN 꼴로 나올 것입니다. 결정 문제의 답이 Y가 되는 최댓값을 찾아주면 됩니다.

결정 문제

이때, 배열 안의 수 중에서 임의의 수 $M$보다 작거나 같은 수의 개수를 셀 방법이 필요합니다. 문제에서 2차원 배열의 각 원소는 $i \times j$ ($1 \leq i, j \leq N$)이므로, $i$번 행의 모든 원소는 $i$의 배수임을 알 수 있습니다.

이를 통해, $M$보다 작거나 같은 $i$의 배수의 개수를 $i = 1, \cdots, N$에 대해 합산하면 전체 배열에서 $M$보다 작거나 같은 수의 개수를 구할 수 있습니다.

def check(m):
    cnt = 0
    for i in range(1, N + 1):
        cnt += min(m // i, N)
    return cnt

결정 문제 구현

이진 탐색

이진 탐색을 통해 결정 문제의 답이 Y(참)이 되는 최댓값을 찾아야 합니다.

먼저, 이진 탐색의 초기 범위를 $[1, K]$로 설정합니다. 최대 범위가 $N \times N$이 아니라 $K$인 이유는, 정렬된 배열에서 $K$번째 수는 $K$ 이하임이 자명하기 때문입니다.

2차원 배열의 각 칸의 원소가 구성되는 방식을 살펴보면, 1을 제외한 모든 원소는 전부 같은 원소가 2개 이상 존재합니다. 따라서, 이를 1차원 배열로 만든 뒤 정렬한 배열의 $K$번째 수는 항상 $K$보다 작거나 같습니다.

low = 1
high = K
 
# 결정문제를 임의의 자연수 m에 대해 전체 2차원 배열에 있는 m 이하의 수의 개수가 K 이하인가? 로 뒀을 때
# YYYY...YNNNN이 되는 Y의 최댓값을 찾아야 한다.
while low <= high:
    mid = (low + high) // 2

    # mid보다 작거나 같은 수의 개수가 K개보다 작을 때 (그래야 K번째 수가 mid가 된다.)
    if (check(mid) < K):
        low = mid + 1
    else:
        high = mid - 1

print(low)

이진 탐색

전체 코드

input = open(0).readline

N = int(input())
K = int(input())

def check(m):
    cnt = 0
    for i in range(1, N + 1):
        cnt += min(m // i, N)
    return cnt

low = 1
high = K
 
# 결정문제를 임의의 자연수 m에 대해 전체 2차원 배열에 있는 m 이하의 수의 개수가 K 이하인가? 로 뒀을 때
# YYYY...YNNNN이 되는 Y의 최댓값을 찾아야 한다.
while low <= high:
    mid = (low + high) // 2

    # mid보다 작거나 같은 수의 개수가 K개보다 작을 때 (그래야 K번째 수가 mid가 된다.)
    if (check(mid) < K):
        low = mid + 1
    else:
        high = mid - 1

print(low)

solution.py