https://www.acmicpc.net/problem/1300
한 달 전에 풀었던 문젠데 진짜 기억이 1도 안난다.
그만큼 이해가 안되셨다는 거겠지~ 🤗
nxn
크기의 배열 a
의 a[i][j] = i x j
일때,
a
배열의 모든 값들을 일차원 배열 b
에 넣고, 오름차순 했을 때 k
번째에 위치한 b[k]
를 구하면 된다.
먼저 k
보다 작은 수의 곱이 몇개인지 찾으면 된다.
k
보다 작은 수가 몇개인지 찾아내면 k
가 몇번째 숫자인지 알아낼 수 있기 때문이다.
코드의 mid
는 b
리스트를 일렬로 나열했을 때, cnt
번째 값을 나타낸다.
즉, a
배열에서 mid 보다 작은 값의 개수가 cnt개인 것이다.
start, end = 0, k
k번째 수는 k보다 클 수 없기 때문에 최댓값으로 정해주었다.
while start <= end:
mid = (start+end) // 2
cnt = 0
for i in range(1,n+1):
cnt += min(mid // i, n)
ex) '10 x 10'에서 20 보다 작거나 같은 수는
1x1 ~ 1x10 = 10개
2x1 ~ 2x10 = 10개
3x1 ~ 3x6 = 6개
...
즉 (20 // 1) + (20 // 2) + (20 // 3) + ... + (20 // 10) 이다.
= ( k // 1 ) + ( k // 2 ) + ... ( k // n)그런데 이 때 (20 // 1) 처럼 n보다 큰 경우가 존재한다.
따라서 최대 n을 갖도록 해준다.min(mid // i, n)
if cnt >= k:
answer = mid
end = mid - 1
else:
start = mid + 1
k보다 작은 수의 개수인 cnt가 k와 같거나 k보다 클 땐,
answer 변수에 mid를 넣어준다.
import sys
input = sys.stdin.readline
n = int(input())
k = int(input())
start, end = 0, k
# k번째 수는 k보다 클 수 없음
while start <= end:
mid = (start+end) // 2
cnt = 0
for i in range(1,n+1):
cnt += min(mid//i, n)
# print("[cnt]:",cnt)
if cnt >= k:
answer = mid
end = mid - 1
else:
start = mid + 1
print(answer)