내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
백준 온라인 저지 (BOJ)
»
K번째 수
ps:problems:boj:1300
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== K번째 수 ====== ===== 풀이 ===== * N개의 수가 주어졌을때, X보다 작은 수의 갯수를 세는 것이 O(T)에 가능하다면, K번째 수는 파라메트릭 서치를 이용해서 O(TlogN)에 찾을 수 있다. K번째 수는 'a_1, ..., a_N 중에서, a_i보다 작은 수의 갯수가 K-1개 이상인 가장 작은 a_i' 로 표현할 수 있기 때문이다. * 이 테크닉을 사용하는 대표적인 다른 예시로 [[ps:구간 쿼리]]가 있다. 머지소트트리를 사용해서 X보다 작은 수의 갯수를 O(log^2(n))에 셀 수 있고, 이것을 이진탐색으로 반복해서 O(log^3(n))에 구간 내 K번째 수를 찾을 수 있다. * 여기서도 같은 방법을 사용한다. i*j로 만들어질수 있는 수 중에서 X보다 작은 수의 갯수를 세는 것은, i를 1,2,...,N으로 증가시키면서 i*j<X인 j의 갯수를 더하는 방식으로 가능하다. i=K일때 이러한 j의 갯수는 %%min((X-1)/K, N)%%으로 O(1)에 구할수 있고, 따라서 모든 i에 대한 j의 갯수의 합은 O(N)에 구할수 있다. * 살짝 더 효율적으로 하면, i가 [1, X/N] 범위에 있을때는 모든 가능한 j값 [1,N]에 대해서 i*j <= X 가 된다. 따라서, i의 루프를 1~N에 돌릴 필요 없이 (X/N + 1)에서 N까지만 돌리는 것으로 충분하다. * 답의 범위가 1~N^2 이므로, X보다 작은 수의 갯수를 세는 것을 O(log(N^2)) = O(logN)번 해야 한다. 따라서 총 시간 복잡도는 O(NlogN) * 구현할때 신경써야 할 부분은 'X보다 작은수의 갯수가 K-1개 이상인 가장 작은 X'를 [1,N^2]의 모든 자연수 중에서 찾았을때, 그 X가 i*j로 표현되는 수라는 보장은 없다. 이것을 처리 하기 위한 간단한 방법은, 'X보다 작은수의 갯수가 **K**개 이상인 가장 작은 X'를 찾는 것이다. 이렇게 하면 X-1이 i*j로 표현되는 K번째 수가 된다는 것은 쉽게 증명 가능하다. ===== 코드 ===== <dkpr py> """Solution code for "BOJ 1300. K번째 수". - Problem link: https://www.acmicpc.net/problem/1300 - Solution link: http://www.teferi.net/ps/problems/boj/1300 """ from teflib import algorithm def main(): def is_greater_than_k_nums(num): low = (num - 1) // N smaller_num_count = low * N smaller_num_count += sum((num - 1) // i for i in range(low + 1, N + 1)) return smaller_num_count >= k N = int(input()) k = int(input()) print(algorithm.binary_search(0, k + 10, is_greater_than_k_nums) - 1) if __name__ == '__main__': main() </dkpr> * Dependency: [[:ps:teflib:algorithm#binary_search|teflib.algorithm.binary_search]] {{tag>BOJ ps:problems:boj:골드_3}}
ps/problems/boj/1300.txt
· 마지막으로 수정됨: 2021/07/19 15:33 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로