[Baekjoon] 1300. K번째 수 [G2]

📚 문제

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

---

📖 풀이

N이 100000까지 주어진다. 그러면 배열을 만들어서 넣으려면 시간초과가 발생한다.

다른 방법을 생각해봐야 한다..

예제의 입력을 보면,

n = 3, k = 7

예제를 배열로 만들어보면 다음과 같다.

1 2 3

2 4 6

3 6 8

오름차순으로 정렬

1 2 2 3 3 4 6 6 8

7번째 수는 6이다.

배열의 규칙성을 보면 행이 바뀔 때마다 2를 곱한다.

그러면 다음 규칙을 알 수 있다.

첫 줄은 1 ~ n

두 번째 줄은 2 ~ 2n, 2간격

세 번째 줄은 3 ~ 3n, 3간격

이 규칙성을 이용해 매개변수 탐색을 활용한다.

표로 작성해본다.

입력 x	1	2	3	4	5	6	7	8
작거나 같은 수의 개수	1	3	5	6	6	8	8	9
탐색 결과(7이상인지)	x	x	x	x	x	o	o	o

탐색할 때 입력된 수보다 작거나 같은 수의 개수가 입력된 7이상이면 o, 아니면 x이다.

o중 맨 왼쪽 값을 이진탐색으로 구한다.

이진탐색할 때 개수구하는 방법은 입력된 x를 1부터 나눈 몫을 더한다. 이 때 나눈 몫이 n보다 크면 n을 더한다.

예제로 보면 n이 3이므로 x가 5인 경우를 보면,

5 // 1 = 5, n보다 작으므로 n인 3을 더한다.

5 // 2 = 2, 두 번째 줄은 5보다 작은 것이 1개이다.

5 // 3 = 1, 세 번째 줄도 하나 있다.

따라서 총 6개가 나온다.

위 방법을 토대로 이진탐색으로 답을 찾는다.

📒 코드

def check(x):
    cnt = 0
    for i in range(1, n + 1):
        cnt += min(n, x // i)
    return cnt >= k

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

s, e = 1, n * n
ans = 0
while s <= e:
    mid = (s + e) // 2
    if check(mid):
        e = mid - 1
        ans = mid
    else:
        s = mid + 1
print(ans)

🔍 결과