백준 1300
-
백준 1300 K번째 수Algorithm/BOJ 2021. 1. 26. 14:53
출처: https://www.acmicpc.net/problem/1300 분류: 이분탐색 접근방식 풀이 자체는 그냥 이진탐색을 이용하면 돼서 그렇게 어렵지 않지만, 이진탐색으로 접근하기가 어려웠던 문제였습니다. 가장 첫 번쨰 접근은 오름차순으로 정렬했을 때 k번째 수라는 건, B[k] 의 원소보다 작거나 같은 수가 k-1개만큼은 있다는 의미가 됩니다. 그럼 B[k]의 원소가 될 어떤 수를 정하고 이 어떤 수보다 작은 수가 k-1개가 있는지 확인하면 됩니다. 문제는 어떤 수보다 작은 수가 몇 개인지 확인하는 방법입니다. 이 방법만 찾으면 이진탐색으로 어떤 수보다 작은 수의 개수가 k보다 작은지 비교해가며 찾아줄 수 있습니다. 어떤 수를 m이라고 했을 때 이 m보다 작은 수가 몇 개가 있는지는 어떻게 확인할..