-
백준(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보다 작은 숫자들의 개수가 된다.
'알고리즘 풀이 > 백준(Boj)' 카테고리의 다른 글
백준(BOJ) 17281번 ⚾ (0) 2020.02.20 백준(BOJ) 17837번 새로운 게임 2 (0) 2020.02.11 백준(BOJ) 17825번 주사위 윷놀이 (0) 2020.01.23 백준(BOJ) 16974번 레벨 햄버거 (0) 2020.01.18 백준(BOJ) 16957번 체스판 위의 공 (0) 2020.01.16