BOJ 1300 K번째 수
https://www.acmicpc.net/problem/1300
시간 2초, 메모리 128MB
input :
- 배열의 크기 N (1 ≤ N ≤ 100,000)
- k (min(10^9, N^2))
output :
- B[k]를 출력
조건 :
-
배열에 들어있는 수 A[i][j] = i×j
-
일차원 배열 B, 오름차순 정렬했을 때, B[k]
1 2 3
2 4 6
3 6 9
1 2 2 3 3 4 6 6 9
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16
01 02 03 04 05
02 04 06 08 10
03 06 09 12 15
04 08 12 16 20
05 10 15 20 25
01 02 03 04 05 06
02 04 06 08 10 12
03 06 09 12 15 18
04 08 12 16 20 24
05 10 15 20 25 30
06 12 18 24 30 36
방법을 계속 몰랐다. 모든 숫자를 정렬해야 하나 하는 이상한 사고만 하고 있었다.
다음 풀이 때 생각할 방법
- 특정 숫자를 지정한다면?
- 해당하는 수보다 작은 놈들을 어떻게 셀 수 있을까?
- 빠르게 탐색?
-> 1. 3. 에 대해서 이분 탐색을 사용하고
-> 2. 에 대해서 반복문을 돌며 해당하는 배열에서 자기 보다 작은 놈을 찾는다.
규칙으로는 구구단이라는 것이었다. 근데 이거 보다 나눗셈을 해서 몫을 체크 하면 해당하는 개수를 알 수 있다는 것이 유효하다.
import sys
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
low, high = 1, n * n
while low <= high:
mid = (low + high) // 2
cnt = 0
for i in range(1, n + 1):
if mid % i != 0:
cnt += min(n, mid // i)
else:
cnt += min(n, mid // i - 1)
if cnt + 1 > k:
high = mid - 1
else:
low = mid + 1
print(high)
Author And Source
이 문제에 관하여(BOJ 1300 K번째 수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/BOJ-1300-K번째-수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)