wookje.dance/2017/02/20/boj-1300-K%EB%B2%88%EC%A7%B8-%EC%88%98/
[BOJ] 1300 : K번째 수
1300 : K번째 수 풀이 임의의 숫자 m을 골라서 K번째 숫자인지 판단해보자! 그 임의의 숫자 m은 무려 O(log K)에! 무려 이분 탐색으로 찾아보자! 그렇다면 떠오르는 질문, m 보다 작은 숫자의 개수를 어
wookje.dance
N = 4일 때
배열 A =
[1, 2, 3, 4]
[2, 4, 6, 8]
[3, 6, 9, 12]
[4, 8, 12, 16]
풀이
임의의 숫자 m을 골라서 K번째 숫자인지 판단해보자!
그 임의의 숫자 m은 무려 O(log K)에! 무려 이분 탐색으로 찾아보자!
그렇다면 떠오르는 질문, m 보다 작은 숫자의 개수를 어떻게 하면 빠르게 구할 수 있을까?
A[i][j]에서, i행에 속한 숫자들은 i*j이므로 모두 i의 배수이다.
그러므로 min(mid/i, N)이 i번째 행에서 mid보다 작은(= 임의의 m보다 작은) 숫자들의 개수가 된다.
eg. N = 1000인 경우, 첫 mid가 1000*1000/2 = 50만이 되는데, 50만/i가 N을 넘어갈 수 있으므로 min(mid/i, N)을 해준다.
조금 더 쉽게 쓰자면, i행의 숫자들은 i*1, i*2, i*3, ..., i*N으로 구성되어 있다. i행의 숫자들 중 m보다 작거나 같은 숫자는 (i*j <= m)를 만족하는 j의 개수이고 이는 i*1, i*2, ..., i*j이므로, m/i와 같은 값이 된다.
각 O(log K)에 대해, 1부터 N까지 모든 i행에 대해 m/i를 수행해주어야 하므로
총 시간 복잡도는 O(NlogK)가 된다.
N, K = int(input()), int(input())
start, end = 1, K
while start <= end:
mid = (start + end) // 2
temp = 0
for i in range(1, N+1):
temp += min(mid//i, N) #mid 이하의 i의 배수 or 최대 N
if temp >= K: #이분탐색 실행
answer = mid
end = mid - 1
else:
start = mid + 1
print(answer)
'BOJ' 카테고리의 다른 글
[BinarySearch] 게임 1072 (0) | 2020.12.08 |
---|---|
[BinarySearch w/LIS] 반도체설계 (0) | 2020.12.06 |
[BinarySearch] 가장 긴 증가하는 부분 수열 2 (0) | 2020.12.03 |
[BinarySearch] 수들의 합 (0) | 2020.12.01 |
[BinarySearch] 공유기 설치 (0) | 2020.12.01 |
댓글