[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)
🔍 결과
Author And Source
이 문제에 관하여([Baekjoon] 1300. K번째 수 [G2]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yunhlim/Baekjoon-1300.-K번째-수-G2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)