1300
-
백준(BOJ 1300) K번째 수알고리즘 풀이/백준(Boj) 2020. 2. 7. 17:49
제목 : https://www.acmicpc.net/problem/1300 1300번: K번째 수 첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, n2)보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 : 임의의 숫자 mid를 통해 K 번째 숫자인지 확인해보자 이때 순차적 탐색은 n이 10만 이므로 이분 탐색을 통해 해결하였다. 후보들은 모두 i*j 값이기 때문에 i의 배수들이고 min(mid/i, N)이 i번째 행에서 mid보다 작은 숫자들의 개수가 된다.